A closure concept based on neighborhood unions of independent triples (Q1313822): Difference between revisions

The paper studies existence conditions for Hamiltonian circuits in graphs. By \(N(u)\) the neighborhood of \(u\), i.e. the set of all vertices adjacent to the vertex \(u\) in a graph \(G\), is denoted. For two vertices \(u\) and \(v\) let \(\lambda_{uv}=| N(u) \cap N(v) |\). Let \(T_{uv}\) (or simply \(T)\) be the set of all vertices different from \(u\), \(v\) and non-adjacent to anyone of the vertices \(u\) and \(v\). A certain condition is formulated, called the 1-2-3-condition. The main result is the following: Theorem. Let \(u\) and \(v\) be two non-adjacent vertices of a 2-connected graph \(G\) of order \(n\). If \(\lambda_{uv} \geq 3\) and \(| N(u) \cup N(v) \cup N(w) | \geq n-\lambda_{uv}\) for at least \(t+2- \lambda_{uv}\) vertices \(w \in T\), or if \(\lambda_{uv} \leq 2\) and \(G\) satisfies the 1-2-3-condition and \(| N(u) \cup N(v) \cup N(w) |=n-3\) for all vertices \(w \in T\), then \(G\) is Hamiltonian if and only if \(G+uv\) is Hamiltonian. Here \(t\) denotes the number of elements of \(T\).