✦ LIBER ✦

Packing bipartite graphs

✍ Scribed by A. Pawel Wojda; Paul Vaderlind

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 383 KB
Volume: 164
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00065-9

No coin nor oath required. For personal study only.

✦ Synopsis

For two bipartite graphs G = (L, R; E) and G' = (L', R'; E') a bijection f: LwR --* L'uR' such that f(L) = L' is called hi-placement when f(u)f(v)~E', for every edge uv ~ E (then G and G' are called hi-placeable).

We give new sufficient conditions for bipartite graphs G and G' to be bi-placeable. When As(G) = AR(G') = 1 (i.e. when all vertices of R and R' are pendent or isolated), we prove a necessary and sufficient condition for G and G' to be bi-placeable.

📜 SIMILAR VOLUMES

Packing two bipartite graphs into a comp

Packing two bipartite graphs into a complete bipartite graph

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

On packing trees into complete bipartite

On packing trees into complete bipartite graphs

✍ Raphael Yuster 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 124 KB

Packing two forests into a bipartite gra

Packing two forests into a bipartite graph

✍ Wang, Hong 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an ( a , b)-bipartition if G has a bipartition ( X , Y ) such that /XI = a and ( Y / = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit ( a , b)-bipartitions. In this note, w

Koszul Bipartite Graphs

✍ Hidefumi Ohsugi; Takayuki Hibi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 48 KB

Cellular Bipartite Graphs

✍ Hans-Jürgen Bandelt; Victor Chepoi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 310 KB

Bipartite Steinhaus graphs

✍ Wayne M. Dymacek 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 523 KB

## Theorem. A Steinhaus graph is bipartite if and only if it has no triangles. Theorem. If G is a bipartite Steinhaus graph (G ~-~) with partitions X and Y, where Ixl-< IYI, then G has an X-saturated matching.