Hamiltonicity in graphs with few \(P_ 4\)'s (Q1805009)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Hamiltonicity in graphs with few \(P_ 4\)'s |
scientific article; zbMATH DE number 751368
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Hamiltonicity in graphs with few \(P_ 4\)'s |
scientific article; zbMATH DE number 751368 |
Statements
Hamiltonicity in graphs with few \(P_ 4\)'s (English)
0 references
15 August 1995
0 references
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.
0 references
scattering number
0 references
\(P_ 4\)-structure
0 references
hamiltonicity
0 references
path covering number
0 references
