Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)-Free Graphs
Authors:
- Andreas BrandstädtABAndreas Brandstädt
- Feodor F. DraganFDFeodor F. Dragan
- Ekkehard KöhlerEKEkkehard Köhler
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 30 (5) , 1662-1677
Abstract
We prove that claw-free graphs, containing an induced dominating path, have a Hamiltonian path, and that 2-connected claw-free graphs, containing an induced doubly dominating cycle or a pair of vertices such that there exist two internally disjoint induced dominating paths connecting them, have a Hamiltonian cycle. As a consequence, we obtain linear time algorithms for both problems if the input is restricted to (claw,net)-free graphs. These graphs enjoy those interesting structural properties.Keywords
This publication has 19 references indexed in Scilit:
- Closure and stable Hamiltonian properties in claw-free graphsJournal of Graph Theory, 2000
- Graph Theory for Programmers2000
- Forbidden subgraphs, hamiltonicity and closure in claw-free graphsDiscrete Mathematics, 1999
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free GraphsSIAM Journal on Computing, 1999
- Closure and Hamiltonian-connectivity of claw-free graphsDiscrete Mathematics, 1999
- Minimal 2-connected non-hamiltonian claw-free graphsDiscrete Mathematics, 1998
- Asteroidal Triple-Free GraphsSIAM Journal on Discrete Mathematics, 1997
- Claw-free graphs — A surveyDiscrete Mathematics, 1997
- Every 3‐connected, locally connected, claw‐free graph is Hamilton‐connectedJournal of Graph Theory, 1996
- A linear time algorithm to compute a dominating path in an AT-free graphInformation Processing Letters, 1995