A note on hamiltonian cycles in \(K_{1,r}\)-free graphs (Q2761058)
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: A note on hamiltonian cycles in \(K_{1,r}\)-free graphs |
scientific article; zbMATH DE number 1682920
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on hamiltonian cycles in \(K_{1,r}\)-free graphs |
scientific article; zbMATH DE number 1682920 |
Statements
17 December 2001
0 references
hamiltonian cycle
0 references
minimum degree sum
0 references
0.9470732
0 references
0.9298201
0 references
0 references
0 references
0.9151663
0 references
A note on hamiltonian cycles in \(K_{1,r}\)-free graphs (English)
0 references
A graph \(G\) is \(K_{1,r}\)-free if \(G\) does not contain a copy of \(K_{1,r}\) as an induced subgraph. Denote by \(\sigma_3(G)\) the minimum degree sum over all triples of independent vertices of \(G\). Main results: (i) every 2-connected \(K_{1,r}\)-free graph \(G\) \((r\geq 5)\) of order \(n\) with \(\sigma_3(G)\geq n+r-3\) is hamiltonian unless \(G-E(G-T)\) (where \(T\) is any maximum independent set in \(G\)) is isomorphic to \(K_{r-1,r-2}\); (ii) every 1-tough \(K_{1,r}\)-free graph \(G\) \((r\geq 5)\) of order \(n\) with \(\sigma_3(G)\geq n+r-5\) is hamiltonian.
0 references
