Paths partition with prescribed beginnings in digraphs: A Chvátal–Erdős condition approach - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2008

Paths partition with prescribed beginnings in digraphs: A Chvátal–Erdős condition approach

Stéphane Bessy

Résumé

A digraph D verifies the Chvátal–Erdős conditions if , where is the stability number of D and is its vertex-connectivity. Related to the Gallai–Milgram Theorem (see Gallai and Milgram [Verallgemeinerung eines Graphentheorischen Satzes von Redei, Acta Sci. Math. 21 (1960) 181–186]), we raise in this context the following conjecture. For every set of vertices , there exists a vertex-partition of D into directed paths such that begins at for all i. The case of the conjecture is proved.

Dates et versions

lirmm-00324584 , version 1 (25-09-2008)

Identifiants

Citer

Stéphane Bessy. Paths partition with prescribed beginnings in digraphs: A Chvátal–Erdős condition approach. Discrete Mathematics, 2008, 308 (18), pp.4108-4115. ⟨10.1016/j.disc.2007.07.113⟩. ⟨lirmm-00324584⟩
180 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More