Hamiltonicity in graphs with few P_ 4's

DOI10.1007/BF02253613MaRDI QIDQ1805009zbMATH OpenOpenAlexFDO

Authors 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

\(P_ 4\)-structurehamiltonicitypath covering numberscattering number

Mathematics Subject Classification ID

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

Review text

R. Jamison and S. Olariu developed, starting from an extension of the notion of cograph, a theory of decomposition of graphs into \(P_ 4\)- connected components. It turned out in their work that the algorithmic idea to exploit the unique tree structure of cographs can be generalized to graphs with simple \(P_ 4\)-structure. This paper shows that deciding hamiltonicity and computing the path covering number are easy tasks for \(P_ 4\)-sparse and \(P_ 4\)-extendible graphs.

Recommendations

• On extended P₄-reducible and extended P₄-sparse graphs
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• scientific article; zbMATH DE number 1375569

Cites work

• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A tree representation for \(P_ 4\)-sparse graphs
• AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS
• An optimal path cover algorithm for cographs
• Complement reducible graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• On a class of posets and the corresponding comparability graphs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• Tough graphs and Hamiltonian circuits.

Cited in

(12)

• Triangulating graphs with few \(P_4\)'s
• Scattering number and modular decomposition
• 1-tough cocomparability graphs are hamiltonian
• A fast parallel algorithm to recognize P4-sparse graphs
• Recognition and isomorphism of tree-like \(P_4\)-connected graphs
• On the \(P_4\)-components of graphs
• scientific article; zbMATH DE number 5952195 (Why is no real title available?)
• The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs
• Solution to an open problem on 4-ordered Hamiltonian graphs
• scientific article; zbMATH DE number 5257394 (Why is no real title available?)
• Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
• Parameterized algorithms in smooth 4-regular Hamiltonian graphs

This page was built for publication: Hamiltonicity in graphs with few \(P_ 4\)'s

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1805009)