Independent cycles and paths in bipartite balanced graphs
Beata Orchel ; A. Paweł Wojda
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 535-549 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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 ki≥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 C2k₁,...,C2kₗ, unless G=K3,3-3K1,1.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270321 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1425,
     author = {Beata Orchel and A. Pawe\l\ Wojda},
     title = {Independent cycles and paths in bipartite balanced graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {535-549},
     zbl = {1173.05029},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1425}
}

Beata Orchel; A. Paweł Wojda. Independent cycles and paths in bipartite balanced graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 535-549. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1425/

[000] [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. | Zbl 0796.05029

[001] [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. | Zbl 0693.05048

[002] [3] B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978).

[003] [4] P.A. Catlin, Subgraphs of graphs, I, Discrete Math. 10 (1974) 225-233, doi: 10.1016/0012-365X(74)90119-8.

[004] [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. | Zbl 0118.19001

[005] [6] M. El-Zahar, On circuits in graphs, Discrete Math. 50 (1984) 227-230, doi: 10.1016/0012-365X(84)90050-5. | Zbl 0548.05037

[006] [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. | Zbl 0791.05080

[007] [8] L. Lesniak, Independent cycles in graphs, J. Comb. Math. Comb. Comput. 17 (1995) 55-63. | Zbl 0820.05040

[008] [9] B. Orchel, Placing bipartite graphs of small size I, Folia Scientarum Universitatis Technicae Resoviensis 118 (1993) 51-58.

[009] [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. | Zbl 0859.05054

[010] [11] M. Woźniak, Packing of graphs (Dissertationes Mathematicae CCCLXII, Warszawa, 1997).

[011] [12] H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404, doi: 10.1016/0012-365X(88)90232-4. | Zbl 0685.05036