PDF

Discussiones Mathematicae Graph Theory 28(3) (2008) 535-549
DOI: https://doi.org/10.7151/dmgt.1425

INDEPENDENT CYCLES AND PATHS IN BIPARTITE BALANCED GRAPHS

Beata Orchel  and  A. Paweł Wojda

Faculty of Applied Mathematics
AGH University of Science and Technology
Al. Mickiewicza 30, 30-059 Kraków, Poland
e-mail: orchel@uci.agh.edu.pl
e-mail: wojda@uci.agh.edu.pl

Abstract

Bipartite graphs G = (L,R;E) and H = (L′,R′;E′) are bi-placeabe if there is a bijection f:L∪R→ L′∪R′ such that f(L) = L′ and f(u)f(v) ∉ E′ for every edge uv ∈ E. We prove that if G and H are two bipartite balanced graphs of order |G| = |H| = 2p ≥ 4 such that the sizes of G and H satisfy ||G|| ≤ 2p−3 and ||H|| ≤ 2p−2, and the maximum degree of H is at most 2, then G and H are bi-placeable, unless G and H is one of easily recognizable couples of graphs.

This result implies easily that for integers p and k₁,k₂,...,k_l such that k_i ≥ 2 for i = 1,... ,l and k₁+... + k_l ≤ p−1 every bipartite balanced graph G of order 2p and size at least p²−2p+3 contains mutually vertex disjoint cycles C_2k1,... ,C_2kl, unless G = K_3,3−3K_1,1.

Keywords: bipartite graphs, bi-placing, path, cycle.

2000 Mathematics Subject Classification: 05C38, 05C35.

References

[1]	M. Aigner and S. Brandt, Embedding arbitrary graphs of maximum degree two, J. London Math. Soc. (2) 48 (1993) 39-51, doi: 10.1112/jlms/s2-48.1.39.
[2]	D. Amar, I. Fournier and A. Germa, Covering the vertices of a graph by cycles of prescribed length, J. Graph Theory 13 (1989) 323-330, doi: 10.1002/jgt.3190130307.
[3]	B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978).
[4]	P.A. Catlin, Subgraphs of graphs, I, Discrete Math. 10 (1974) 225-233, doi: 10.1016/0012-365X(74)90119-8.
[5]	K. Corrádi and A. Hajnal, On the maximal number of independent circuits in a graph, Acta. Math. Acad. Sci. Hungar. 14 (1963) 423-439, doi: 10.1007/BF01895727.
[6]	M. El-Zahar, On circuits in graphs, Discrete Math. 50 (1984) 227-230, doi: 10.1016/0012-365X(84)90050-5.
[7]	J.-L. Fouquet and A.P. Wojda, Mutual placement of bipartite grahps, Discrete Math. 121 (1993) 85-92, doi: 10.1016/0012-365X(93)90540-A.
[8]	L. Lesniak, Independent cycles in graphs, J. Comb. Math. Comb. Comput. 17 (1995) 55-63.
[9]	B. Orchel, Placing bipartite graphs of small size I, Folia Scientarum Universitatis Technicae Resoviensis 118 (1993) 51-58.
[10]	H. Wang, On the maximum number of independent cycles in a bipartite graph, J. Combin. Theory (B) 67 (1996) 152-164, doi: 10.1006/jctb.1996.0037.
[11]	M. Woźniak, Packing of graphs (Dissertationes Mathematicae CCCLXII, Warszawa, 1997).
[12]	H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404, doi: 10.1016/0012-365X(88)90232-4.

Received 23 May 2008
Accepted 14 July 2008