×

A note on careful packing of a graph. (English) Zbl 0831.05054

Suppose \(G_1, \ldots, G_k\) are graphs of order \(n\). We say that there is a packing of \(G_1, \ldots, G_k\) (into the complete graph \(K_n)\) if there exist injections \(\alpha_i : V(G_i) \to V (K_n)\), \(i = 1, \ldots, k\), such that \(\alpha^*_i (E(G_i)) \cap \alpha^*_j (E(G_j)) = \varnothing\) for \(i \neq j\), where the map \(\alpha^*_i : E(G_i) \to E(K_n)\) is induced by \(\alpha_i \). A careful packing of a graph \(G\) of order \(n\) is a packing of a cycle \(C_n\) and two copies of \(G\) into \(K_n\). In other words, a careful packing of a graph \(G\) of order \(n\) is a packing of 2 copies of \(G\) into \(K_n - E(C_n)\). It is well known that there is a packing of two copies of a graph \(G\) (of order \(n)\) into \(K_n\) if \(e(G) \leq n-2\). In this paper the following theorem is proved by induction on \(n\): Let \(G\) be a graph of order \(n \geq 6\). If \(e(G) \leq n - 2\), then there exists a careful packing of \(G\) except for two graphs of order 6: \(K_3\cup K_2\cup K_1\) and \(C_4 \cup 2 K_1\), and for two families of graphs: \(K_{1,n - 2} \cup K_1\) and \(K_{1,n - 3} \cup K_2\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory

Keywords:

careful packing
PDFBibTeX XMLCite
Full Text: DOI Link