Forbidden subgraphs, hamiltonicity and closure in claw-free graphs
type: Item
instance of: scholarly article
title: Forbidden subgraphs, hamiltonicity and closure in claw-free graphs
zbMATH Open document ID: 0927.05053
DOI: 10.1016/S0012-365X(98)00334-3
author: Jan Brousek
author: Zdeněk Ryjáček
author: Odile Favaron
published in: Discrete Mathematics
publication date: 1999-09-29T00:00:00Z
review text: The stability of classes of graphs defined by forbidden subgraph conditions under the closure defined by \textit{Z. Ryjáček} [J. Comb. Theory, Ser. B 70, No. 2, 217-224 (1997; Zbl 0872.05032)] is studied. In particular, it is shown that the following classes of graphs are stable for all positive integers \(i, j, k\): \(\text{CP}_i\)-free graphs, \(\text{CZ}_i\)-free graphs, and \(\text{CN}_{i,j,k}\)-free graphs. The class of \(\text{CB}_{i,j}\)-free graphs are shown to not be stable. Using the stability results, some classes of graphs defined by forbidden subgraph conditions are shown to either be hamiltonian or belong to a special class of exceptional graphs. For example, it is proved that any \(2\)-connected \(\text{CP}_7\)-free graph is either hamiltonian or belongs to one exceptional class of \(2\)-connected graphs constructed from edge disjoint complete graphs. These results extend some of the classical results on forbidden graphs that imply hamiltonian.
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1321786
zbMATH Keywords: hamiltonian
zbMATH Keywords: forbidden subgraphs
zbMATH Keywords: claw-free
zbMATH Keywords: closure
reviewed by: Ralph Faudree
MaRDI profile type: Publication
cites work: The edge Hamiltonian path problem is NP-complete
cites work: Q5422499
cites work: Q3211339
cites work: Minimal \(2\)-connected non-Hamiltonian claw-free graphs
cites work: Q3918148
cites work: Claw-free graphs---a survey
cites work: Q3838206
cites work: Characterizing forbidden pairs for hamiltonian properties
cites work: Q4862340
cites work: Sufficient conditions for a graph to be Hamiltonian
cites work: Forbidden subgraphs and Hamiltonian properties and graphs
cites work: On a closure concept in claw-free graphs
cites work: Hamiltonicity in claw-free graphs
Wikidata QID: Q127532707
description: scientific article; zbMATH DE number 1321786