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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Aug 29, 2017 at 9:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .