DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

J. Wang

Jieyan Wang

Moscow High School

email: jieyan.wang17@gmail.com

Title:

Packing trees in complete bipartite graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 42(1) (2022) 263-275

Received: 2019-03-19 , Revised: 2019-09-26 , Accepted: 2019-09-26 , Available online: 2019-11-05 , https://doi.org/10.7151/dmgt.2252

Abstract:

An embedding of a graph $H$ in a graph $G$ is an injection (i.e., a one-to-one function) $\sigma$ from the vertices of $H$ to the vertices of $G$ such that $\sigma (x)\sigma (y)$ is an edge of $G$ for all edges $xy$ of $H$. The image of $H$ in $G$ under $\sigma$ is denoted by $\sigma (H)$. A $k$-packing of a graph $H$ in a graph $G$ is a sequence $(\sigma_1,\sigma_2,\ldots, \sigma_k)$ of embeddings of $H$ in $G$ such that $\sigma_1(H),\sigma_2(H),\ldots,\sigma_k(H)$ are edge disjoint. We prove that for any tree $T$ of order $n$, there is a $4$-packing of $T$ in a complete bipartite graph of order at most $n+12$.

Keywords:

packing, placement, edge-disjoint tree, bipartite graph

References:

  1. D. Burns and S. Schuster, Embedding $(p,p-1)$-graphs in their complements, Israel J. Math. 30 (1978) 313–320.
    https://doi.org/10.1007/BF02761996
  2. A. Gyárfás and J. Lehel, Packing trees of different order into $K_n$, Colloq. Math. Soc. János Bolyai 18 (1978) 463–469.
  3. S.P. Haler and H. Wang, Packing four copies of a tree into a complete graph, Australas. J. Combin. 59 (2014) 323–332.
  4. J.M. Harris, J. Hirst and M.J. Mossinghoff, Combinatorics and Graph Theory (Springer, New York, 2010).
    https://doi.org/10.1007/978-0-387-79711-3
  5. B. Orchel, $2$-placement of $(p,q)$-trees, Discuss. Math. Graph Theory 23 (2003) 23–26.
    https://doi.org/10.7151/dmgt.1183
  6. H. Wang and N. Sauer, Packing three copies of a tree into a complete graph, European J. Combin. 14 (1993) 137–142.
    https://doi.org/10.1006/eujc.1993.1018
  7. H. Wang, Packing two forests into a bipartite graph, J. Graph Theory 23 (1996) 209–213.
    https://doi.org/10.1002/(SICI)1097-0118(199610)23:2<209::AID-JGT12>3.0.CO;2-B
  8. H. Wang, Packing three copies of a tree into a complete bipartite graph, Ann. Comb. 13 (2009) 261–269.
    https://doi.org/10.1007/s00026-009-0022-0
  9. M. Woźniak, Packing of graphs and permutations–-a survey, Discrete Math. 276 (2004) 379–391.
    https://doi.org/10.1016/S0012-365X(03)00296-6
  10. H.P. Yap, Packing of graphs–-a survey, Discrete Math. 72 (1988) 395–404.
    https://doi.org/10.1016/0012-365X(88)90232-4

Close