✦ LIBER ✦

Hamiltonian circuits in chordal bipartite graphs

✍ Scribed by Haiko Müller

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 359 KB
Volume: 156
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00057-4

No coin nor oath required. For personal study only.

✦ Synopsis

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 of the HAMILTONIAN PATH problem coincides with the complexity of HAMILTONIAN CIRCUIT. Further, we show that HAMIL-TONIAN CIRCUIT is linear-time solvable for convex bipartite graphs.

📜 SIMILAR VOLUMES

Treewidth of Chordal Bipartite Graphs

✍ T. Kloks; D. Kratsch 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 743 KB

Chordal bipartite graphs are exactly those bipartite graphs in which every cycle of length at least six has a chord. The treewidth of a graph \(G\) is the smallest maximum cliquesize among all chordal supergraphs of \(G\) decreased by one. We present a polynomial time algorithm for the exact computa

Perfect Elimination and Chordal Bipartit

Perfect Elimination and Chordal Bipartite Graphs

✍ Martin Charles Golumbic; Clinton F. Goss 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 348 KB

## Abstract We define two types of bipartite graphs, chordal bipartite graphs and perfect elimination bipartite graphs, and prove theorems analogous to those of Dirac and Rose for chordal graphs (rigid circuit graphs, triangulated graphs). Our results are applicable to Gaussian elimination on spars

Hamiltonian circuits in Cayley graphs

✍ Dragan Marušič 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 268 KB

Hamiltonian circuits in random graphs

✍ L. Pósa 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 807 KB

Tough enough chordal graphs are Hamilton

Tough enough chordal graphs are Hamiltonian

✍ Chen, Guantao; Jacobson, Michael S.; K�zdy, Andr� E.; Lehel, Jen? 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB 👁 3 views

We prove that every 18-tough chordal graph has a Hamiltonian cycle.

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