𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Hamiltonian bipartite graphs

✍ Scribed by J. Moon; L. Moser

Book ID
112884956
Publisher
The Hebrew University Magnes Press
Year
1963
Tongue
English
Weight
133 KB
Volume
1
Category
Article
ISSN
0021-2172

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Line graphs of bipartite graphs with Ham
Line graphs of bipartite graphs with Hamiltonian paths
✍ Francis K. Bell πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 115 KB

It is shown that, if t is an integer !3 and not equal to 7 or 8, then there is a unique maximal graph having the path P t as a star complement for the eigenvalue Γ€2: The maximal graph is the line graph of K m,m if t ΒΌ 2mΓ€1, and of K m,m ΓΎ1 if t ΒΌ 2m. This result yields a characterization of L(G ) wh

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