Packing trees into complete bipartite graphs

作者：Hollingsworth Susan^*

来源：Discrete Mathematics, 2013, 313(8): 945-948.

DOI：10.1016/j.disc.2013.01.016

• Trees
• Packing
• Bipartite
• Balanced

In 1976, Gyarfas and Lehel conjectured that any trees T-2, ... , T-n with 2 through n vertices pack into K-n, the complete graph on n vertices, that is, the trees T-2, ... , T-n appear as edge-disjoint subgraphs of K-n. This conjecture is still unresolved.
We examine an analogous conjecture for packing trees into complete bipartite graphs. Let T-a,T-a denote a tree whose partite sets both have size a, which we call a balanced tree. We conjecture that any trees T-1,T-1, ... , T-n,T-n pack into K-n,K-n, the complete bipartite graph on 2n vertices.
We begin by establishing that if a and n are integers with n >= 3 and a < left perpendicular root 7/18nright perpendicular, then any balanced trees T-1,T-1, ... , T-a,T-a pack into K-n,K-n.
We also show that if any degree sequence for the first partite set is specified for each tree, then there exist balanced trees T-1,T-1, ... , T-n,T-n with these vertex degrees that pack into K-n,K-n.

• 出版日期2013-4-28