×

Packing three copies of a tree into a complete graph. (English) Zbl 0773.05084

A graph \(G\) of order \(n\) is said to be 3-placeable if there are three edge-disjoint copies of \(G\) in the complete graph \(K_ n\). M. Woźniak and A. Wojda (unpublished) proved that every graph \(G\) of order \(n\) and size at most \(n-2\) is 3-placeable if \(G\neq K_ 3\cup 2K_ 1\) or \(K_ 4\cup 4K_ 1\). In this paper the authors prove that every tree \(T\) of order \(n\geq 7\) having maximum degree at most \(n-3\) is 3-placeable.
The reviewer takes the opportunity to say that in 1992 T. Hasunuma and Y. Shibata of Gunma University, Japan, also proved the same result independently.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI