4
$\begingroup$

A couple of questions related to edge-disjoint cycles.

Let $K_n = (V,E)$ be the complete graph on $|V|=n$ nodes. Two cycles are 'edge disjoint' if they do not share any edges.

  • What is the size of the largest collection of edge-disjoint cycles of length 3 in Kn?

  • Consider a spanning tree sub-graph of $K_n$ (so any spanning tree on $n$ nodes). Is there an efficient algorithm for adding $c$ edges such that each edge creates a cycle of length 3 and is edge-disjoint with all other cycles added?

Any references or ideas would be greatly appreciated!

thanks...

$\endgroup$
4
  • 1
    $\begingroup$ If I understand the second question correctly, you want $c\le n/2$? $\endgroup$ Nov 20, 2011 at 12:31
  • $\begingroup$ The first question does not quite make sense. Do you want the size of the maximal collection of edge-disjoint triangles? $\endgroup$
    – Igor Rivin
    Nov 20, 2011 at 12:33
  • 3
    $\begingroup$ $n \equiv 1,3 \mod 6$ iff there is a Steiner triple system on $n$ points, which is equivalent to a partition of the edges of $K_n$ into triangles. $\endgroup$ Nov 20, 2011 at 13:07
  • $\begingroup$ Thanks for the quick replies. Yes, I meant the size of the maximal collection of edge-disjoint triangles. I updated the post accordingly. For the maximum value of c in the second question, that would be upper bounded by the answer to the first question. Thanks for the Steiner triple reference, I will look into that. $\endgroup$
    – dan
    Nov 20, 2011 at 13:21

1 Answer 1

12
$\begingroup$

The maximum number of edge-disjoint triangles in a complete graph is determined by:

Joel Spencer. Maximal consistent families of triples. J. Combinatorial Theory, 5 1968 1–8.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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