# Independent cycles and paths in bipartite balanced graphs

Discussiones Mathematicae Graph Theory (2008)

- Volume: 28, Issue: 3, page 535-549
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topBeata Orchel, and A. Paweł Wojda. "Independent cycles and paths in bipartite balanced graphs." Discussiones Mathematicae Graph Theory 28.3 (2008): 535-549. <http://eudml.org/doc/270321>.

@article{BeataOrchel2008,

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ₗ 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\}$.},

author = {Beata Orchel, A. Paweł Wojda},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {bipartite graphs; bi-placing; path; cycle},

language = {eng},

number = {3},

pages = {535-549},

title = {Independent cycles and paths in bipartite balanced graphs},

url = {http://eudml.org/doc/270321},

volume = {28},

year = {2008},

}

TY - JOUR

AU - Beata Orchel

AU - A. Paweł Wojda

TI - Independent cycles and paths in bipartite balanced graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2008

VL - 28

IS - 3

SP - 535

EP - 549

AB - 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}$.

LA - eng

KW - bipartite graphs; bi-placing; path; cycle

UR - http://eudml.org/doc/270321

ER -

## References

top- [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. Zbl0796.05029
- [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. Zbl0693.05048
- [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. Zbl0118.19001
- [6] M. El-Zahar, On circuits in graphs, Discrete Math. 50 (1984) 227-230, doi: 10.1016/0012-365X(84)90050-5. Zbl0548.05037
- [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. Zbl0791.05080
- [8] L. Lesniak, Independent cycles in graphs, J. Comb. Math. Comb. Comput. 17 (1995) 55-63. Zbl0820.05040
- [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. Zbl0859.05054
- [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. Zbl0685.05036

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.