Independent cycles and paths in bipartite balanced graphs

Beata Orchel; A. Paweł Wojda

Discussiones Mathematicae Graph Theory (2008)

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

Abstract

top
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 2 k ₁ , . . . , C 2 k ₗ , unless G = K 3 , 3 - 3 K 1 , 1 .

How to cite

top

Beata 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. [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. [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. [3] B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978). 
  4. [4] P.A. Catlin, Subgraphs of graphs, I, Discrete Math. 10 (1974) 225-233, doi: 10.1016/0012-365X(74)90119-8. 
  5. [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. [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. [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. [8] L. Lesniak, Independent cycles in graphs, J. Comb. Math. Comb. Comput. 17 (1995) 55-63. Zbl0820.05040
  9. [9] B. Orchel, Placing bipartite graphs of small size I, Folia Scientarum Universitatis Technicae Resoviensis 118 (1993) 51-58. 
  10. [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. [11] M. Woźniak, Packing of graphs (Dissertationes Mathematicae CCCLXII, Warszawa, 1997). 
  12. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.