Covering the edges of a graph by a prescribed tree with minimum overlap (Q1386432)

Let \(H\) be a graph, and let \(k\) be a positive integer. If there is a covering of a graph \(G\) by copies of \(H\) such that no edge of \(G\) is covered more than \(k\) times, then \(G\) is said to be \(H\)-coverable with overlap \(k\). The minimum \(k\) for which \(G\) is \(H\)-coverable with overlap \(k\) is denoted by overlap\((H,G)\). We define the redundancy of a covering which uses \(t\) copies of \(H\) as \((t| E_H| -| E_G|)/ | E_G| \). The authors show that if \(H\) is a tree of order \(h\) and \(G\) is a graph with minimum degree \(\delta(G) \geq (2h)^{10}+ C\), where \(C\) is an absolute constant, then overlap\((H,G)\) is at most 2. They further show that such a covering with overlap 2 and redundancy at most \(1.5/(\delta(G))^{0.1}\) can be found. The authors also prove that for every tree \(H\) of order at least 4 and for every function \(f\), the problem of deciding if a graph \(G\) with minimum degree at least \(f(h)\) has overlap\((H,G)=1\) is NP-complete.