Welcome to MathOverflow

Question

0

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...

edited Nov 20 2011 at 13:18

asked Nov 20 2011 at 12:08

dan
227●10

If I understand the second question correctly, you want $c\le n/2$? – Gjergji Zaimi Nov 20 2011 at 12:31

The first question does not quite make sense. Do you want the size of the maximal collection of edge-disjoint triangles? – Igor Rivin Nov 20 2011 at 12:33

2

$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. – Douglas Zare Nov 20 2011 at 13:07

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. – dan Nov 20 2011 at 13:21

Brendan McKay · Accepted Answer · 2011-11-20 15:41:26Z UTC

9

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.

answered Nov 20 2011 at 15:41

Brendan McKay
9,120●1●13●33

graph_tizzy · Answer 2 · 2012-10-18 21:21:00Z UTC

0

could someone explain this in an easy to understand way - How many edge-disjoint cycles of length 3 are in the complete graph?

answered Oct 18 at 21:21

graph_tizzy
1

How many edge-disjoint cycles of length 3 are in the complete graph?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.