Two theorems on packings of graphs (Q1090341)

Two graphs G, H of the same order are called packable if G can be embedded in the complement \(\bar H\) of H. The main results of the present paper: Theorem 1 states that two non-star graphs of order \(p\geq 5\) and size p-1 are packable with exception of specified 13 pairs. Theorem 2 gives a complete characterization when a tree on p vertices and a graph of order p size p form a couple of packable graphs. This represents a generalization of various known results by Sauer, Spencer, Burns, Schuster, Slater and the authors.