Packing three trees

DOI10.1016/0012-365X(95)00204-AMaRDI QIDQ1916129zbMATH OpenFDO

Publication date 13 January 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00204-A

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Suppose \(G_1, G_2,\dots, G_k\) are graphs of order at most \(n\). Then there is a packing of \(G_1, G_2,\dots, G_k\) into the complete graph \(K_n\) if there exist injections \(\alpha_i: V(G_i)\to V(K_n)\), \(i= 1,2,\dots, n\), such that \(\alpha^*_i(E(G_i))\cap \alpha^*_j(E(G_j))= \varnothing\) for \(i\neq j\), where \(\alpha^*_i: E(G_i)\to E(K_n)\) is induced by \(\alpha_i\). The main result of this paper is Theorem 10: Any three trees of order \(n- 1\) can be packed into \(K_n\). Note that A. M. Hobbs, B. A. Bourgeois and J. Kasiraj had earlier proved that three trees \(T_1\), \(T_2\), \(T_3\) of orders \(n_1< n_2< n_3= n\), respectively, can be packed into \(K_n\), see Discrete Math. 67, 27-42 (1987; Zbl 0642.05043). H. Wang and N. Sauer had proved that if \(T\) is a tree of order \(n\geq 6\) and \(T\neq S_n\) (a star), \(S_n'\) (a tree obtained by subdividing an edge of \(S_{n- 1})\), \(S_6\) (\(S_n\) is a tree obtained by replacing an edge of \(S_{n- 2}\) by a path of length 3), then three isomorphic copies of \(T\) can be packed into \(K_n\), see Eur. J. Comb. 14, No. 2, 137-142 (1993; Zbl 0773.05084).

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Packing three trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1916129)