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/