Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge?

For example, consider $K_4$ with vertices $V=${1,2,3,4}. It can be decomposed into the union:

$K_4=$ {{1,2},{3,4}} $\cup$ {{1,3},{2,4}} $\cup$ {{1,4},{2,3}}

In this example, none of the 3 subgraphs share an edge. For $n$ odd, I could easily find a general decomposition of $K_n$ into $n$ "independent" maximal matching subgraphs:

$K_n= \bigcup_\sigma$ { {$\sigma(1),\sigma(n-1)$}, {$\sigma(2),\sigma(n-2)$}, ... }

where the union is over all cyclic permutations $\sigma$ of the vertex set $V=${1,2,...,$n$}. For $n$ even, however, I can't find a general solution for this decomposition problem, which would involve the union of $n-1$ subgraphs. I can solve it for particular examples, like $K_4$, $K_6$ and $K_8$, but not for the general $n$ even case.

share|improve this question

1 Answer 1

up vote 9 down vote accepted

Let the $2n$ vertices be the $2n-1$ vertices of a regular polygon and its center. Join the center to one of the other vertices by a line segment $S$, then join the remaining $2n-2$ vertices in pairs by line segments perpendicular to $S$. That's one maximal matching subgraph. Now rotate the vertices around the center through $2\pi k/n$, $k=1,2,\dots,$, while keeping the line segments where they are. That will give you the rest of the maximal matching subgraphs which together decompose $K_{2n}$.

share|improve this answer
1  
Agreed, and note that this is called a 1-factorization or perfect factorization of $K_{2n}$. Searching on those phrases will uncover a large amount of theory including other constructions. –  Brendan McKay Oct 17 '11 at 21:24
    
That's it! The solution is so simple! I feel ashamed. Thank you very much, Gerry! –  helvio Oct 17 '11 at 21:33
    
Thank you for the input, Brendan. I am totally ignorant about graph theory, I only took a glance at it yesterday and today to try to understand this particular combinatorial problem. I will try to learn more into 1-factorization and perfect factorization, as it might be useful in my computer program I'm developing. –  helvio Oct 17 '11 at 21:38
    
Is there a similar decomposition involving a "n-gonal prism" that produces n isomorphic factors? Gerhard "Ask Me About System Design" Paseman, 2011.10.17 –  Gerhard Paseman Oct 17 '11 at 21:41
    
@Gerhard: I don't know about that case, but there is a significant theory of whether the complete graph can be decomposed into copies of some specified graph. There are lots of theorems but also lots of open problems. Put "graph decomposition" (with the quotes) into google scholar. Someone who could tell you about the case of prisms is Darryn Bryant. –  Brendan McKay Oct 18 '11 at 1:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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