pith. sign in

arxiv: 1607.01456 · v1 · pith:GW2TIVEAnew · submitted 2016-07-06 · 🧮 math.CO · cs.DM

Decomposing 8-regular graphs into paths of length 4

classification 🧮 math.CO cs.DM
keywords decompositionpathsadmitsconjecturededgesgraphkouiderlength
0
0 comments X
read the original 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 $2\ell$-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 $\mathcal{D}$ where every vertex of $G$ is the end-vertex of exactly two paths of $\mathcal{D}$, 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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.