PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2008 | 28 | 3 | 535-549
Tytuł artykułu

Independent cycles and paths in bipartite balanced graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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}$.
Słowa kluczowe
Wydawca
Rocznik
Tom
28
Numer
3
Strony
535-549
Opis fizyczny
Daty
wydano
2008
otrzymano
2008-05-23
zaakceptowano
2008-07-14
Twórcy
autor
  • Faculty of Applied Mathematics, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Kraków, Poland
  • Faculty of Applied Mathematics, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Kraków, Poland
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1425
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.