DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

J. Wang

Title:

Packing trees in complete bipartite graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-03-19, Revised: 2019-09-24, Accepted: 2019-09-26, 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

PDF
Close