4

1

Let $G$ be a $(2k+1)$-regular graph on $n$ vertices. A theorem by Lovasz implies that $G$ decomposes into $\frac{1}{2}n$ disjoint paths.

Since the number of edges is $\frac{1}{2}n(2k +1)$, is it possible to require that each path in the decomposition be of size $(2k +1)$.

I found an argument for the case when the graph $G$ has a perfect matching and its girth $\geq 2k +1$. Is there any literature on this.

flag

3 Answers

6

The question is "no" in general, as Gjergji pointed out. The question of when the answer is "yes" is difficult and only partial results are known. It is conjectured that having a 1-factor is sufficient. A recent paper that discusses the issue is this paper of Odile Favaron, François Genest and Mekkia Kouider. Here is the abstract:

Kotzig asked in 1979 what are necessary and sufficient conditions for a $d$-regular simple graph to admit a decomposition into paths of length $d$ for odd $d\gt 3$. For cubic graphs, the existence of a 1-factor is both necessary and sufficient. Even more, each 1-factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1-factor. We conjecture that existence of a 1-factor is indeed a sufficient condition for Kotzig’s problem. For general odd regular graphs, most 1-factors appear to be extendable and we show that for the family of simple 5-regular graphs with no cycles of length 4, all 1-factors are extendable. However, for $d\gt 3$ we found infinite families of $d$-regular simple graphs with non-extendable 1-factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5-regular graphs all 1-factors are extendable.

Finally, I should mention that I'm not a specialist in this area so my assertion that the problem is still unsolved is not gospel.

link|flag
This is very useful! What a fun problem. Is there an example of an odd d-regular graph without a perfect matching which has a decomposition into paths of length d? – Gjergji Zaimi May 23 2012 at 6:41
Yes, it is a nice problem. The graph $G_1$ in Figure 7 of that paper is an example with degree 5. Problem 3 in that paper is to do it for higher degrees. – Brendan McKay May 23 2012 at 12:18
If $G$ has a perfect matching $M_1$ and and of girth $\gt 2k + 2$, then $G-M_1$ is the union of $k$ $2$-factors $F_1, F_2, ..., F_k$. $(M_1 \cup F_1)$ is a simple 3-regular graph and $M_1$ is extendable into $\frac{1}{2}n$ paths of length $3$. Let $M_2$ be the matching obtained by considering each path as one edge. Similarly in $(M_2 \cup F_2)$, $M_2$ is extendable into $\frac{1}{2}n$ paths of length $3$. Since the girth $\gt 2k + 2$, at each step $F_i \cup M_i$ will be a simple cubic graph and the process could be continued until the desired paths are obtained. – hbm May 24 2012 at 9:36
6

The answer in general is no. Already in the case $k=1$, a cubic graph is the disjoint union of paths of length $3$ if and only if it has a perfect matching. Proof: If the graph has a decomposition into paths of length $3$, take the middle edges. This will give you a perfect matching. For the other direction, suppose you have a perfect matching $M$. The complement of $M$ is a union of cycles which we can orient arbitrarily. Now to each edge in $M$ assign an outgoing and an incoming edge.

Determining which graphs admit decompositions into paths of length $k$ seems to be hard in general. In addition to the conjectures mentioned in Brendan Mckay's answer let me mention another closely related conjecture. Let's call a $k$-PPDC (perfect path double cover) a decomposition of the edges of our graphs taken with multiplicity 2, into paths of length $k$ so that each vertex appears exactly twice as an endpoint of such a path. It is conjectured that every k-regular graph admits a k-PPDC (see "Perfect path double covers of graphs" by J.A. Bondy where this conjecture is proved for k-regular graphs of girth greater than k). Notice that for $(2k+1)$-regular graphs, a path decomposition as in your problem implies a $(2k+1)$-PPDC. I don't even know the answer to this weaker conjecture for $k\geq 2$: If a $(2k+1)$-regular graph has a perfect matching, does it have a $(2k+1)$-PPDC?

link|flag
I can't figure out this similar reasoning, could you expand? – Will Sawin May 22 2012 at 19:00
1 
 @Will. Suppose a (2k+1)-regular graph can be written as a union of paths of length 2k+1. For each such path we orient the two 'end' edges towards each other. I claim that the oriented edges are a 2-factor. To see this, note that each vertex must have out-degree at least one, since it's degree is odd. On the other hand, the number of oriented edges is n, so each vertex has out-degree exactly 1 (and hence in-degree exactly 1). Removing the oriented edges and applying induction, we get the stronger result of a decomposition into 2-factors and one leftover 1-factor. – Tony Huynh May 22 2012 at 19:32
Petersen showed that every regular graph of even degree can be decomposed into 2-factors, so a regular graph $G$ of odd degree $2k+1$ can be decomposed into $k$ 2-factors and one 1-factor iff that 1-factor exists. A sufficient (but not necessary) condition is that $G$ is $2k$-edge-connected. – Brendan McKay May 23 2012 at 1:03
@Tony: I didn't get your "and hence in-degree exactly 1" since digraphs can easily have all out-degrees 1 and a mixture of in-degrees. – Brendan McKay May 23 2012 at 1:10
1 
 @Tony: Here is a counterexample. Decompose $K_6$ into paths 1-2-6-3-5-4, 3-1-4-2-5-6 and 5-1-6-4-3-2. Taking the end edges oriented inwards does not make a 2-factor. The middle edges do not make a 1-factor either. – Brendan McKay May 23 2012 at 3:43
show 3 more comments
0

do u know algorithm of finding the decomposition of complete graph into path size n-1 to 1?

link|flag

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.