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 the normal view instead:

scientific article; zbMATH DE number 495858
Language Label Description Also known as
default for all languages
No label defined
    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
      0 references
      Hamiltonicity
      0 references
      connectivity
      0 references
      independence number
      0 references
      0 references

      Identifiers