A new result on local forbidden graph and hamiltonicity (Q1913915)
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 new result on local forbidden graph and hamiltonicity |
scientific article; zbMATH DE number 883565
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A new result on local forbidden graph and hamiltonicity |
scientific article; zbMATH DE number 883565 |
Statements
A new result on local forbidden graph and hamiltonicity (English)
0 references
22 January 1997
0 references
Let \(G= (V, E)\) be a graph of order \(n\), \(V_0= \{v\in V\mid \deg(v)\geq {n\over 2}\}\), \(\overline V_0= V\backslash V_0\), \(G[\overline V_0]\) the subgraph of \(G\) induced by the vertices of \(\overline V_0\) and \(F\) the unique graph with degree sequence 333111 (often also denoted by \(N\) and referred to as the net). The following conjecture by Zhu is proved. If \(G\) is a 3-connected graph such that \(G[\overline V_0]\) contains no induced subgraph \(F\) and each induced subgraph \(K_{1, 3}\) of \(G\) has at least one endvertex in \(V_0\), then \(G\) is hamiltonian.
0 references
VD-cycle
0 references
hamiltonian
0 references
0.8353018760681152
0 references
0.8277877569198608
0 references
0.8233855962753296
0 references
0.8224328756332397
0 references