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$
  • 1
    $\begingroup$ If I understand the second question correctly, you want $c\le n/2$? $\endgroup$ – Gjergji Zaimi Nov 20 '11 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 '11 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$ – Douglas Zare Nov 20 '11 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 '11 at 13:21
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, privacy policy and cookie policy

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