- Tytuł:
- Independent cycles and paths in bipartite balanced graphs
- Autorzy:
-
Orchel, Beata
Wojda, A. - Powiązania:
- https://bibliotekanauki.pl/articles/743087.pdf
- Data publikacji:
- 2008
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
bipartite graphs
bi-placing
path
cycle - Opis:
- 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}$.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2008, 28, 3; 535-549
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł