Skip to main content
2 of 4
added 61 characters in body
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43

The most up to date account on the minimum number of subsets for a $(v,k,2)$ covering is here:

Y. M. Chee, C. J. Colbourn, A. C. H. Ling, R. M. Wilson, Covering and packing for pairs, J. Combin. Theory Ser. A 120 (2013) 1440–1449.

One important remark about Thomas Kalinowski's answer is that the asymptotic solution by Caro and Yuster may be incomplete, although the claimed upper bound is likely the correct one. They rely on Gustavsson's theorem on graph decomposition (Lemma 2.1 in Caro and Yuster's paper), which is claimed to be proved in the following thesis:

T. Gustavsson, ``Decompositions of Large Graphs and Digraphs with High Minimum Degree,'' Doctoral Dissertation, Dept. of Mathematics, Univ. of Stockholm, 1991.

However, here's an excerpt from the 2013 paper by Chee, Colbourn, Ling, and Wilson:

Their approach relies in an essential manner on a strong statement by Gustavsson:

Proposition 1.1: . Let $H$ be a graph with $v$ vertices and $h$ edges, having degree sequence $(d_1,\dots,d_v)$. Then there exist a constant $N_H$ and a constant $\epsilon_H>0$, both depending only on $H$, such that for all $n>N_H$, if $G$ is a graph on $n$ vertices, $m$ edges, and degree sequence $(\delta_1,\dots,\delta_n)$ so that $\min(\delta_1,\dots,\delta_n) \geq n(1−\epsilon_H)$, $\gcd(d_1,\dots,d_v)\ \vert\ \gcd(\delta_1,\dots,\delta_n)$, and $h\ \vert\ m$, then $G$ has an edge partition (decomposition) into graphs isomorphic to $H$.

We have not been able to verify the proof of Proposition 1.1. Indeed, while the result has been used a number of times in the literature, no satisfactory proof of it appears there. While we expect that the statement is true, we do not think that the proof in [12] is sufficient at this time to employ the statement as a foundation for further results. Therefore we adopt a strategy that is completely independent of Proposition 1.1, and independent of the results built on it.

So, one might want to be careful about Caro and Yuster's claimed solution. Chee, Colbourn, Ling, and Wilson gave a slightly weaker upper bound on the minimum size of a $(v,k,2)$ covering, which essentially states that for sufficiently large $v$, Caro and Yuster's claimed upper bound is correct within a constant that depends on $k$.

Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43