Author(s) | |
---|---|
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. |
Format | |
Publication Date |
2000-01-01
|
Publication Title |
SIAM Journal on Computing
|
Volume |
30
|
Issue |
5
|
First Page |
1662
|
Last Page |
1677
|
Subject | |
Community | |
Comments | |
Recommended Citation |
Brandstädt, Andreas; Dragan, Feodor F; Köhler, Ekkehard (2000). Linear Time Algorithms or Hamiltonian Problems on (Claw, Net)-Free Graphs. SIAM Journal on Computing 30(5) 1662-1677. Retrieved from https://oaks.kent.edu/cspubs/4
|
Copyright 2000 Society for Industrial and Applied Mathematics.