A special case of the tree packing conjecture

Marcus E Gubanyi

Abstract


The Tree Packing Conjecture of Gyárfás states that for any set of n-1 trees T = {T₁, T₂, …, Tn-1}, where Ti has i edges, T can be packed into Kn. We define a family of trees called two-spiders that are almost stars, and show that packings of Kn with two-spiders can be constructed by exchanging edges of known packings. We prove that if each tree Ti ∈ T is a two-spider and has at most α i two-legs for α = (3-√5)/4, then T packs into Kn.

Keywords


tree; packing; complete graph

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.11

References

J. Balogh and C. Palmer, "On the Tree Packing Conjecture," SIAM Journal on Discrete Mathematics, vol. 27, pp. 1995–2006, 2013.

J. Böttcher, J. Hladký, D. Piguet, and A. Taraz, "An approximate version of the tree packing conjecture," Israel Journal of Mathematics, vol. 211, no. 1, pp. 391–446, 2016.

E. Dobson, "Packing Almost Stars into the Complete Graph," Journal of Graph Theory, vol. 25, pp. 169–172, 1997.

E. Dobson, "Packing Trees of Bounded Diameter into the Complete Graph," Australasian Journal of Combinatorics, vol. 37, pp. 89–100, 2007.

A. Gyárfás and J. Lehel, "Packing Trees of Different Orders into K_n," in Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1986), Colloquia Mathematica Societatis János Bolyai, vol. 18, pp. 463–469, 1978.

Y. Roditty, "Packing and covering of the complete graph. III. On the tree packing conjecture," Sci. Ser. A Math. Sci. (NS), vol. 1, pp. 81–85, 1988.

H. Yap, "Packing of graphs – a survey," Annals of Discrete Mathematics, vol. 38, pp. 395–404, 1988.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats