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 Access content directly
Journal Articles Discrete Mathematics Year : 2008

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

Stéphane Bessy

Abstract

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 and versions

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

Identifiers

Cite

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⟩
177 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More