Journal of the
Korean Mathematical Society JKMS

Let $G$ be a bipartite graph with $(X,Y)$ as its bipartition. Let $B$ be a complete bipartite graph with a bipartition $(V_1,V_2)$ such that $X\subseteq V_1$ and $Y\subseteq V_2$. A {\em bi-packing} of $G$ in $B$ is an injection $\sigma$: $V(G) \rightarrow V(B)$ such that $\sigma (X)\subseteq V_1$, $\sigma (Y)\subseteq V_2$ and $E(G)\cap E(\sigma (G))=\emptyset$. In this paper, we show that if $G$ is a bipartite graph of order $n$ with girth at least 12, then there is a complete bipartite graph $B$ of order $n+1$ such that there is a bi-packing of $G$ in $B$. We conjecture that the same conclusion holds if the girth of $G$ is at least 8.

Keywords: packing, embedding, placement

MSC numbers: 05C70