Orthogonal decomposition and packing of complete graphs (Q1806215): Difference between revisions

A \(k\)-orthogonal \(H\)-decomposition of a graph \(G\) is a set of \(k\) edge-decompositions of \(G\) into copies of \(H\) such that any two copies of \(H\) from different decompositions in the set intersect on at most one edge. The authors prove that there is \(N= N(k,r)\) such that for every \(n>N\), if \(K_n\) has a \(K_r\)-decomposition then it also has a \(k\)-orthogonal \(K_r\)-decomposition. The authors also present a method to find a \(k\)-orthogonal packing of \(K_n\) if \(K_n\) does not have a \(K_r\)-decomposition. They consider the complexity of deciding the existence of \(k\)-orthogonal decompositions and propose the following conjecture: for every fixed graph \(H\) having at least three edges in some connected component, and for every fixed positive integer \(k\), it is NP-complete to decide whether a given input graph has a \(k\)-orthogonal \(H\)-decomposition.