Name
Abstract | ||
|---|---|---|
We examine powers of Hamiltonian paths and cycles as well as Hamiltonian (power) completion problems in several highly structured graph classes. For threshold graphs we give efficient algorithms as well as sufficient and minimax toughness like conditions. For arborescent comparability graphs we have similar results but also show that for one type of completion problem an ·obvious’ minimax condition fails. For cographs we give examples showing that toughness and other ·obvious’ necessary conditions are not sufficient. For threshold graphs we give additional necessary and sufficient conditions in terms of vertex degrees as well as a minimax formula for the length of a longest cycle power. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0012-365X(98)00346-X | Discrete Mathematics |
Keywords | Field | DocType |
arborescent comparability graph,hamiltonian power,hamiltonian path | Discrete mathematics,Combinatorics,Indifference graph,Minimax,Hamiltonian (quantum mechanics),Vertex (geometry),Hamiltonian path,Chordal graph,Hamiltonian path problem,Comparability,Mathematics | Journal |
Volume | Issue | ISSN |
202 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
12 | 0.87 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sam Donnelly | 1 | 12 | 0.87 |
| Garth Isaak | 2 | 172 | 24.01 |