Minimum coverings of crowns with cycles and stars (Q2062674)

Suppose that \(F\), \(G\) and \(H\) are graphs. By a \(G\)-decomposition of \(F\) we mean a partition of \(E(F)\) into copies of \(G\). By a \((G, H)\)-decomposition of \(F\) we mean a partition of \(E(F)\) into copies of \(G\) and copies of \(H\) with at least one copy of \(G\) and at least one copy of \(H\). As a \((G, H)\)-decomposition of \(F\) may or may not exist in general, it is essential to find the minimum number of edges needed to be added to the edge set of \(F\) so that the resulting graph is \((G, H)\)-decomposable. Also it would be interesting to see how the collection of added edges look like. The authors in this paper has done exactly that and found the minimum \((C_k, S_k)\)-covering of the crown \(C_{n,n-1} \), where \(S_k\) is the \(k\)-star graph, \(C_k\) is the cycle of length \(k\) and \(C_{n,n-1} \) is the graph obtained from the complete bipartite graph \(K_{n,n}\) by removing a 1-factor from it. The proof technique is interesting.