On path decompositions of 2k-regular graphs

DOI10.1016/J.ENDM.2015.07.028zbMATH Open1347.05101arXiv1510.02526OpenAlexW2783442670MaRDI QIDQ324765FDOQ324765

Authors: Andrea Jiménez, F. Botler 

Publication date: 17 October 2016

Abstract: Tibor Gallai conjectured that the edge set of every connected graph $G$ on $n$ vertices can be partitioned into $lceiln/2ceil$ paths. Let $mathcal{G}_k$ 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 $mathcal{G}_k$, for every $kgeq3$. Further, we prove that for every graph $G$ in $mathcal{G}_k$ on $n$ vertices, there exists a partition of its edge set into $n/2$ paths of lengths in $2k-1,2k,2k+1$.

Full work available at URL: https://arxiv.org/abs/1510.02526

Recommendations

• On path decompositions of \(2 k\)-regular graphs
• Gallai's conjecture for graphs of girth at least four
• Path decompositions and Gallai's conjecture
• Towards Gallai's path decomposition conjecture
• Decompositions of 6-regular bipartite graphs into paths of length six

zbMATH Keywords

regular graphslength-constrainedpath decompositions

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Path decompositions and Gallai's conjecture
• Covering the edges of a connected graph by paths
• Decompositions of triangle-free 5-regular graphs into paths of length five
• Decomposing graphs into paths of fixed length
• From the theory of regular graphs of third and fourth degree
• Regular path decompositions of odd regular graphs
• Title not available (Why is that?)
• An upper bound for the path number of a graph
• Gallai's Conjecture For Graphs of Girth at Least Four
• Title not available (Why is that?)
• Path decomposition of graphs with given path length

Cited In (7)

• Gallai's path decomposition conjecture for graphs of small maximum degree
• Note on the decomposition of \(\lambda K_{m,n}\) (\(\lambda K^*_{m,n}\)) into paths
• On the existence of uniformly resolvable decompositions of \(K_v\) and \(K_v-I\) into paths and kites
• Title not available (Why is that?)
• Path decompositions of regular graphs with prescribed girth
• Title not available (Why is that?)
• On path decompositions of \(2 k\)-regular graphs

This page was built for publication: On path decompositions of \(2k\)-regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q324765)