×

Path covers of weighted graphs. (English) Zbl 0813.05050

Let \((G,w)\) be an ordered pair where \(G\) is a simple graph and \(w: E(G)\mapsto \{0,1,2\}\) is a weight. A path cover \(\mathcal P\) of \((G,w)\) is a collection of paths in \(G\) such that every edge \(e\) is contained in exactly \(w(e)\) members of \(\mathcal P\). For a vertex \(v\in V(G)\), \(w(v)\) is the sum of the weights of all edges incident with \(v\). A vertex \(v\) is odd (or even) if \(w(v)\) is odd (or even, respectively). In this paper, two very interesting results, with elegant proofs, are obtained: (1) If every vertex of \((G,w)\) is incident with at most one edge of weight two, then \((G,w)\) has a path cover \(\mathcal P\) such that each odd vertex occurs exactly once, and each even vertex occurs exactly twice, as an end of a member of \(\mathcal P\). (2) If every vertex of \((G,w)\) is even, then \((G,w)\) has a path cover \(\mathcal P\) such that each vertex occurs exactly twice as an end of a member of \(\mathcal P\). The first result generalizes a result by Lovász (1968) which is a partial result of a conjecture of Gallai. The second result generalizes a result by H. Li [J. Graph Theory 14, No. 6, 645-650 (1990; Zbl 0725.05054)] which was proposed by J. A. Bondy [J. Graph Theory 14, No. 2, 259-272 (1990; Zbl 0745.05038)] as a conjecture. This path covering problem is a modified version of the well- known cycle double cover conjecture proposed by Szekeres (1973) and Seymour (1979).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] , and , Graphs with the circuit cover property. Preprint.
[2] Bondy, J. Graph Theory 14 pp 259– (1990)
[3] Li, J. Graph Theory 14 pp 645– (1990)
[4] On covering of graphs. Theory of Graphs. Academic Press, New York (1968) 231–236.
[5] Sums of circuits. Graph Theory and Related Topics. Academic Press, New York (1979) 341–355.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.