Bipacking a bipartite graph with girth at least 12
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
Abstract
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.
참고문헌 (9)
- B. Bollobas, "Extremal Graph Theory" (1978), Academic Press, Inc
- S. Brandt, "Graph theory, combinatorics, and algorithms, Vol. 1, 2", pp.115~121 (1995), Wiley-Intersci. Publ, Wiley
- R. J. Faudree, "Embedding graphs in their complements, Czechoslovak Math", Czechoslovak Math. J, 31(1), pp.53~62 (1981)
- J.-L. Fouquet, "Mutual placement of bipartite graphs", Discrete Math, 121, pp.85~92 (1993)
- A. Gorlich, "A note on embedding graphs without short cycles", Discrete Math, 286(1-2), pp.75~77 (2004)
- B. Orchel, "2-placement of (p; q)-trees, Discuss. Math", Graph Theory, 23(1), pp.23~36 (2003)
- N. Sauer, "The chromatic number of the two packings of a forest" (1992), University of Calgary
- H. Wang, "Packing two forests into a bipartite graph", J. Graph Theory, 23(2), pp.209~213 (1996)
- H. Wang, "Packing two bipartite graphs into a complete bipartite graph", J. Graph Theory, 26(2), pp.95~104 (1997)