Wyniki wyszukiwania

1

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

2-placement of (p,q)-trees

100%

Orchel B.

Discussiones Mathematicae Graph Theory

|

2003

|

tom 23

|

nr 1

23-36

EN

Let G = (L,R;E) be a bipartite graph such that V(G) = L∪R, |L| = p and |R| = q. G is called (p,q)-tree if G is connected and |E(G)| = p+q-1. Let G = (L,R;E) and H = (L',R';E') be two (p,q)-tree. A bijection f:L ∪ R → L' ∪ R' is said to be a biplacement of G and H if f(L) = L' and f(x)f(y) ∉ E' for every edge xy of G. A biplacement of G and its copy is called 2-placement of G. A bipartite graph G is 2-placeable if G has a 2-placement. In this paper we give all (p,q)-trees which are not 2-placeable.

2

Placing bipartite graphs of small size II

100%

Orchel B.

Discussiones Mathematicae Graph Theory

|

1996

|

tom 16

|

nr 2

93-110

EN

In this paper we give all pairs of non mutually placeable (p,q)-bipartite graphs G and H such that 2 ≤ p ≤ q, e(H) ≤ p and e(G)+e(H) ≤ 2p+q-1.

3

Independent cycles and paths in bipartite balanced graphs

63%

Orchel B., Wojda A.

Discussiones Mathematicae Graph Theory

|

2008

|

tom 28

|

nr 3

535-549

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

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

3 Orchel B.

1 Wojda A.

1 2008

1 2003

1 1996

2-placement of (p,q)-trees

Placing bipartite graphs of small size II

Independent cycles and paths in bipartite balanced graphs