Covering graphs: The covering problem solved (Q1269896)

Let \(H\) be a fixed graph with \(h\) edges such that the gcd of all degrees of \(H\) is \(d\). The authors prove that for all \(n>n_0(H)\), where \(n_0(H)\) is enormous, the \(H\)-covering number of \(K_n\) is \(\left \lceil {dn\over 2h}\left \lceil {n-1 \over d} \right\rceil \right \rceil\) except for \(d\equiv 0\pmod 2\), \(n\equiv 1 \pmod d\), \(n(n-1)/d+1 \equiv 0\pmod {2h/d}\). In this latter exceptional case, the \(H\)-covering number is \(\left\lceil {n(n-1) \over 2h} \right\rceil+1\). The statement ``the covering problem solved'' is misleading, since most cases one would want occur for \(n<n_0\).