Return to Question

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?

I can suggest the following lower bound: if $n$ is odd, there are $n-1$ edges coming from one vertex. So every $4$-cycle should pass through a vertex $\frac{n-1}{2}$ times. Since a cycle passes through $4$ vertices, we have to use at least $\ge \frac{\frac{n(n-1)}{2}}{4}=\frac{n(n-1)}{8}$ distinct $4$-cycles.

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

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?

I can suggest following lower bound: If $n$ is odd there are $n-1$ edges coming from one vertex. So every $4$-cycle should pass throw a vertex $\frac{n-1}{2}$ times. Since a cycle passes throw $4$ vertices we have number of $4$-cycles $\ge \frac{\frac{n(n-1)}{2}}{4}=\frac{n(n-1)}{8}$

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?

I can suggest the following lower bound: if $n$ is odd, there are $n-1$ edges coming from one vertex. So every $4$-cycle should pass through a vertex $\frac{n-1}{2}$ times. Since a cycle passes through $4$ vertices, we have to use at least $\ge \frac{\frac{n(n-1)}{2}}{4}=\frac{n(n-1)}{8}$ distinct $4$-cycles.

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?

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?

I can suggest following lower bound: If $n$ is odd there are $n-1$ edges coming from one vertex. So every $4$-cycle should pass throw a vertex $\frac{n-1}{2}$ times. Since a cycle passes throw $4$ vertices we have number of $4$-cycles $\ge \frac{\frac{n(n-1)}{2}}{4}=\frac{n(n-1)}{8}$