Some localization Hamiltonian conditions (Q1312923)
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: Some localization Hamiltonian conditions |
scientific article; zbMATH DE number 495858
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Some localization Hamiltonian conditions |
scientific article; zbMATH DE number 495858 |
Statements
Some localization Hamiltonian conditions (English)
0 references
26 January 1995
0 references
The following three results on Hamiltonicity have been obtained. Let \(G\) be a 2-connected graph with \(n (\geq 3)\) vertices. If \(| N(u) \cap N (v) |\) is greater than or equal to the size of the largest induced subgraph containing \(u\) and \(v\) and isomorphic to a star, whenever \(u,v \in V\), \(d(u,v) = 2\) and \(\max (d_ G(u), d_ G(v)) < {n \over 2}\), then \(G\) is Hamiltonian. If \(G\) is a graph of order \(n (\geq 3)\) such that for any vertex \(u\) and any \(x,y \in N (u) \cup \{u\}\) and \(xy \notin E(G)\), \(d_{N(u) \cup \{u\}} (x) + d_{N(u) \cup \{u\}} (y) \geq d_ G (u) + 1\), then \(G\) is Hamiltonian. (I think a condition on connectivity is necessary for this result.) Let \(G\) be a connected graph with \(n (\geq 3)\) vertices. If either \(G\) is complete or \(1 \leq \min \{{| S | \over \alpha (G[N(S)])}:S\) a separating set of \(G\}\), where \(\alpha (G[N(S)])\) is the independence number of the subgraph induced by \(N(S)\) in \(G\), then \(G\) is Hamiltonian. It is conjectured that a connected graph with \(n\) vertices such that for any vertex \(u\), the connectivity of the induced subgraph \(G[N(u) \cup \{u\}]\) is greater than or equal to its independence number \(\alpha (G[N(u) \cup \{u\}])\), is Hamiltonian. These are localizations of some well-known conditions for Hamiltonicity.
0 references
Hamiltonicity
0 references
connectivity
0 references
independence number
0 references