Abstract | ||
---|---|---|
Tibor Gallai conjectured that the edge set of every connected graph G on n vertices can be partitioned into ⌈n∕2⌉ paths. Let Gk be the class of all 2k-regular graphs of girth at least 2k−2 that admit a pair of disjoint perfect matchings. In this work, we show that Gallai’s conjecture holds in Gk, for every k≥3. Further, we prove that for every graph G in Gk on n vertices, there exists a partition of its edge set into n∕2 paths of lengths in {2k−1,2k,2k+1} and cycles of length 2k. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.disc.2016.09.029 | Discrete Mathematics |
Keywords | DocType | Volume |
Path decomposition,Length-constrained,
2k-regular graphs,Perfect matchings | Journal | 340 |
Issue | ISSN | Citations |
6 | 0012-365X | 3 |
PageRank | References | Authors |
0.49 | 5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Fábio Botler | 1 | 26 | 7.51 |
Andrea Jiménez | 2 | 8 | 4.13 |