✦ LIBER ✦

Hamiltonian cycles in bipartite graphs

✍ Scribed by Xiaoyun Lu

Publisher: Springer-Verlag
Year: 1995
Tongue: English
Weight: 389 KB
Volume: 15
Category: Article
ISSN: 0209-9683
DOI: 10.1007/bf01200758

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Alternating hamiltonian cycles in two co

Alternating hamiltonian cycles in two colored complete bipartite graphs

✍ A. G. Chetwynd; A. J. W. Hilton 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 269 KB 👁 2 views

## Abstract We give necessary and sufficient conditions for the existence of an alternating Hamiltonian cycle in a complete bipartite graph whose edge set is colored with two colors.

Long cycles in bipartite graphs

✍ Bill Jackson 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 735 KB

Partition of a bipartite hamiltonian gra

Partition of a bipartite hamiltonian graph into two cycles

✍ Denise Amar 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 480 KB

We prove the following theorem. "I'neorem. If G is a balanced bipartite graph with bipartition (A, B), [A I = IBI = n, such that for any x ~ A, y ~ B, d(x) + d(y) >>-n + 2, then for any (nl, n2), ni >I 2, n -----n I + hE, G contains two independent cycles of lengths 2nl and 2n2.

Hamiltonian circuits in chordal bipartit

Hamiltonian circuits in chordal bipartite graphs

✍ Haiko Müller 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 359 KB

The main result of this paper is the NP-completeness of the HAMILTONIAN CIRCUIT problem for chordal bipartite graphs. This is proved by a sophisticated reduction from SATISFIABILITY. As a corollary, HAMILTONIAN CIRCUIT is NP-complete for strongly chordal split graphs. On both classes the complexity

Small cycles in Hamiltonian graphs

✍ Uwe Schelten; Ingo Schiermeyer 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 733 KB

We prove that if a graph G on n > 32 vertices is hamiltonian and has two nonadjacent vertices u and u with d(u) + d(u) 3 n + z where z = 0 if n is odd and z = 1 if n is even, then G contains all cycles of length m where 3 < m < 1/5(n + 13).

Dominating cycles in bipartite biclaw-fr

Dominating cycles in bipartite biclaw-free graphs

✍ Daniel Barraez; Evelyne Flandrin; Hao Li; Oscar Ordaz 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 354 KB

Flandrin et ai. (to appear) define a simple bipartite graph to be biclaw-free if it contains no induced subgraph isomorphic to H, where H could be obtained from two copies of K1.3 by adding an edge joining the two vertices of degree 3. They have shown that if G is a bipartite, balanced, biclaw-free