Geodesic
Independent cycles and paths in bipartite balanced graphs
Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 3, pp. 535-549.

Voir la notice de l'article provenant de la source Library of Science

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ₗ such that k_i ≥ 2 for i = 1,...,l and k₁ +...+ kₗ ≤ p-1 every bipartite balanced graph G of order 2p and size at least p²-2p+3 contains mutually vertex disjoint cycles C_2k₁,...,C_2kₗ, unless G = K_3,3 - 3K_1,1.
Keywords: bipartite graphs, bi-placing, path, cycle 
@article{DMGT_2008_28_3_a11,
     author = {Orchel, Beata and Wojda, A.},
     title = {Independent cycles and paths in bipartite balanced graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {535--549},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a11/}
}
TY  - JOUR
AU  - Orchel, Beata
AU  - Wojda, A.
TI  - Independent cycles and paths in bipartite balanced graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2008
SP  - 535
EP  - 549
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a11/
LA  - en
ID  - DMGT_2008_28_3_a11
ER  - 
%0 Journal Article
%A Orchel, Beata
%A Wojda, A.
%T Independent cycles and paths in bipartite balanced graphs
%J Discussiones Mathematicae. Graph Theory
%D 2008
%P 535-549
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a11/
%G en
%F DMGT_2008_28_3_a11
Orchel, Beata; Wojda, A. Independent cycles and paths in bipartite balanced graphs. Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 3, pp. 535-549. http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a11/

[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.