Hamiltonicity in graphs with few \(P_ 4\)'s

DOI10.1007/BF02253613zbMath0819.05042OpenAlexW2025795635MaRDI QIDQ1805009

Winfried Hochstättler, Gottfried Tinhofer

Publication date: 15 August 1995

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02253613

zbMATH Keywords

path covering numberscattering numberhamiltonicity\(P_ 4\)-structure

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Related Items

1-tough cocomparability graphs are hamiltonian, A fast parallel algorithm to recognize P4-sparse graphs, The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs, Recognition and isomorphism of tree-like \(P_4\)-connected graphs, On the \(P_4\)-components of graphs, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, Triangulating graphs with few \(P_4\)'s

Cites Work

• Unnamed Item
• Complement reducible graphs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• On a class of posets and the corresponding comparability graphs
• An optimal path cover algorithm for cographs
• Tough graphs and Hamiltonian circuits.
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS