Covering Graphs: The Covering Problem Solved

For every fixed graphH, we determine theH-covering number ofKn, for alln>n0(H). We prove that ifhis the number of edges ofH, andgcd(H)=dis the greatest common divisor of the degrees ofH, then there existsn0=n0(H), such that for alln>n0,C(H, Kn)=dn2hn−1d,unlessdis even,n=1 mod dandn(n−1)/d+1=0 mod(2h/d), in which case[formula]Our main tool in proving this result is the deep decomposition result of Gustavsson.