Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: bi-placing

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Independent cycles and paths in bipartite balanced graphs

100%

Orchel B., Wojda A.

Discussiones Mathematicae Graph Theory

2008

tom 28

nr 3

535-549

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

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Orchel B.

1 Wojda A.

1 2008

Wyniki wyszukiwania

Independent cycles and paths in bipartite balanced graphs