7
$\begingroup$

I am interested in coverings of the (edge set of the) complete graph $K_n$ by cycles of length $4$. It is clear that such coverings exist for each $n \ge 4$. I need to find the minimum number of $4$-cycles necessary to cover $K_n$.

For example, $K_5$ can be covered by following $4$-cycles $(1, 2, 3, 5), (2, 5, 4, 3), (2, 4, 1, 3)$.

I am sure this problem has been studied but unfortunately can't find any results. Can you share some results?

Since $K_n$ has $\binom{n}{2}$ edges, the minimum number of $4$-cycles is obviously at least $\binom{n}{2} / 4$.

Improve this question
$\endgroup$
7
  • $\begingroup$ You mean, if $n\ge 4$, not 3? $\endgroup$
    – Fedor Petrov
    Aug 29, 2017 at 6:59
  • $\begingroup$ To put this question into the usual contemporary conceptual framework: all the OP is asking for is precisely this: the edge covering number $\rho(\mathcal{H})$ of the hypergraph $\mathcal{H}$ whose ground-set is the edge-set of the complete graph $K_n$ and whose set of hyperedges is equal to the set of edge-sets of all 4-circuits in $K_n$. Please do not be confused by the (traditional) technical term 'edge covering number': this does not refer to covering the edges, rather, the term, regrettably very widespread, refers to a covering of the ground-set by hyperedges. $\endgroup$
    – Peter Heinig
    Aug 29, 2017 at 7:20
  • $\begingroup$ Re 'edge cover': you can remember this by way of the following joke that I once heard: graph-theorists call 'book covers' 'paper covers'. (I.e., the noun modifier gives not the thing-to-be-covered, rather the thing-that-the-cover-is-made-of.) $\endgroup$
    – Peter Heinig
    Aug 29, 2017 at 7:22
  • $\begingroup$ I take it that your question is really for the precise $\rho(\mathcal{H})$ defined in my comment, as a function of $n$, so this is not an answer, yet a very relevant comment: Berger and Ziv proved that for every finite hypergraph $\mathcal{H}$ with rank $r$ and $m$ edges and independence number $\alpha$, we have $\rho(\mathcal{H})\leq\frac{(r-2)m+\alpha}{r-1}$. $\endgroup$
    – Peter Heinig
    Aug 29, 2017 at 7:42
  • $\begingroup$ The hypergraph $\mathcal{H}$ I defined above has precisely $m= \frac12 \binom{n}{4} (4-1)! = 3\binom{n}{4}$ edges, and it has $\alpha=1$ because any two distinct edges of the underlying graph are in a hyperedge of $\mathcal{H}$, so the Berger-Ziv-bound works out to a guarantee that there always is a cover of the kind you require of size at most $\lfloor \frac{(4-2)3\binom{n}{4} + 1}{4-1}\rfloor = \lfloor \frac{n(n-1)(n-2)(n-3)}{12} + \frac13 \rfloor$. While this may be non-obvious upper bound, it's too large. E.g. for $n=5$ it gives $10$, while you gave a covering by $3$ four-circuits. $\endgroup$
    – Peter Heinig
    Aug 29, 2017 at 8:14

2 Answers 2

Reset to default
6
$\begingroup$

If $n$ is odd, the answer is $\lceil \binom{n}{2}/4 \rceil$.

If $n$ is even, the answer is $\lceil \binom{n}{2}/4+n/8 \rceil$.

This follows from two special cases of a more general conjecture by Alspach.

For our purposes, we use a theorem of Heinrich, Horák, and Rosa which says that if $n \geq 7$ is odd and $a,b,c$ are such that $3a+4b+6c=\binom{n}{2}$, then $E(K_n)$ can be partitioned into $a$ $3$-cycles, $b$ $4$-cycles, and $c$ $6$-cycles. Huang and Fu proved the same result with $(3,4,6)$ replaced by $(4,5)$.

Thus, if $n \geq 7$ is odd, it is always possible to decompose $E(K_n)$ into $4$-cycles and possibly one extra cycle that is a $3$-cycle, a $5$-cycle or a $6$-cycle. The edge set of the extra cycle can obviously be covered with two $4$-cycles of $K_n$, so we are done.

If $n$ is even, then each vertex has odd degree. Let $v$ be an arbitrary vertex. Since every $4$-cycle uses $0$ or $2$ edges incident to $v$, there will be at least one edge incident to $v$ that is covered twice. Thus, in total there will be at least $n/2$ edges that are covered twice. Thus, every covering of $E(K_n)$ by $4$-cycles has size at least $\binom{n}{2}/4+n/8$. We prove that this bound can actually be achieved.

Namely, for $n$ even, Heinrich, Horák, and Rosa's result holds except with $K_n$ replaced by $K_n$ minus a perfect matching $M$, and $\binom{n}{2}$ replaced with $\frac{n(n-2)}{2}$. For $n$ even, $\frac{n(n-2)}{2}$ is divisible by $4$. It follows that the edges of $K_n-M$ can be decomposed into $4$-cycles. By then covering pairs of edges of $M$ with $4$-cycles we get a covering of size $\lceil \binom{n}{2}/4+n/8 \rceil$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How are the pairs of edges arranged for the n even case? I see how to do it with about n/4 four cycles, but not with n/8. (Oh, half the cycles are "in n choose 2". Coffee really helps.) Gerhard "Did Something Similar Just Below" Paseman, 2017.08.29. $\endgroup$
    – Gerhard Paseman
    Aug 29, 2017 at 15:28
  • $\begingroup$ Yes, for $n$ even we can use the Paseman Theorem instead of the Heinrich, Horák, Rosa Theorem. $\endgroup$
    – Tony Huynh
    Aug 29, 2017 at 15:39
  • 1
    $\begingroup$ I feel honored. Thanks for your scholarship and contributions. Gerhard "Really, I Do Feel Honored" Paseman, 2017.08.29. $\endgroup$
    – Gerhard Paseman
    Aug 29, 2017 at 15:41
1
$\begingroup$

If n is even, you can form a partial edge cover with disjoint four-cycles: pick points u and v, and cover all edges coming from u and from v (except for uv) by disjoint cycles. Now recurse, leaving n/2 uncovered edges which are covered by n/4 many more cycles. If n is odd, save edges coming from w for later, and cover the remaining n-1 points and edges, leaving 3(n-1)/2 edges to be covered three at a time by cycles going through w. This gives a minimum of about n/4 + n(n-2)/8 many cycles, with exact numbers to come later.

Edit: Tony Huynh has provided exact numbers, with the construction in the paragraph above an alternate proof for even n. For odd n greater than 3, the cycle decomposition using an extra 3 5 or 6 cycle improves on the method above. End Edit.

Gerhard "Bed For Now. Calculations Later." Paseman, 2017.08.29.

Improve this answer
$\endgroup$
1
  • $\begingroup$ For n odd, three at a time may not work, but two at a time should. In any case, we should get within n/2 of the required n(n-1)/8 number of cycles. Gerhard "Will Ponder This While Asleep" Paseman, 2017.08.29. $\endgroup$
    – Gerhard Paseman
    Aug 29, 2017 at 9:16

Your Answer

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

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