Decomposition of 8-regular graphs into paths of length 4

DOI10.1016/J.ENDM.2017.06.032MaRDI QIDQ1689903zbMATH OpenOpenAlexFDO

Authors F. Botler, Alexandre Talon

Publication date 18 January 2018

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

zbMATH Keywords

graph decompositionpathregular graph

Mathematics Subject Classification ID

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

Abstract: A $T$-decomposition of a graph $G$ is a set of edge-disjoint copies of $T$ in $G$ that cover the edge set of $G$. Graham and H"aggkvist (1989) conjectured that any $2ell$-regular graph $G$ admits a $T$-decomposition if $T$ is a tree with $ell$ edges. Kouider and Lonc (1999) conjectured that, in the special case where $T$ is the path with $ell$ edges, $G$ admits a $T$-decomposition $mathcalD$ where every vertex of $G$ is the end-vertex of exactly two paths of $mathcalD$, and proved that this statement holds when $G$ has girth at least $(ell+3)/2$. In this paper we verify Kouider and Lonc's Conjecture for paths of length $4$.

Recommendations

• Decomposing 8-regular graphs into paths of length 4
• Decomposing 2k-regular graphs into paths of length k
• Decomposition of (2k + 1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k + 1
• Decomposing regular graphs with prescribed girth into paths of given length
• Path decompositions of regular graphs with prescribed girth

Cites work

• A survey of graceful trees
• Decomposing regular graphs with prescribed girth into paths of given length
• scientific article; zbMATH DE number 4150219 (Why is no real title available?)
• scientific article; zbMATH DE number 1334640 (Why is no real title available?)
• scientific article; zbMATH DE number 3308125 (Why is no real title available?)

Cited in

(5)

• Decomposition of (2k + 1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k + 1
• Decomposing 8-regular graphs into paths of length 4
• Decomposing regular graphs with prescribed girth into paths of given length
• The complexity of \(P_{4}\)-decomposition of regular graphs and multigraphs
• scientific article; zbMATH DE number 845482 (Why is no real title available?)

This page was built for publication: Decomposition of 8-regular graphs into paths of length 4

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