A closure concept based on neighborhood unions of independent triples
type: Item
instance of: scholarly article
title: A closure concept based on neighborhood unions of independent triples
zbMATH Open document ID: 0789.05059
DOI: 10.1016/0012-365X(92)00049-W
author: Ingo Schiermeyer
author: Hajo Broersma
published in: Discrete Mathematics
publication date: 1994-06-12T00:00:00Z
review text: 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\).
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 500605
zbMATH Keywords: Hamiltonian graph
zbMATH Keywords: closure
zbMATH Keywords: neighborhood unions
zbMATH Keywords: independent triples
zbMATH Keywords: Hamiltonian circuits
MaRDI profile type: Publication
cites work: Semi-independence number of a graph and the existence of Hamiltonian circuits
cites work: Q3866156
cites work: A method in graph theory
cites work: Q5422499
cites work: Q3689218
cites work: Q3474676
cites work: Hamiltonism, degree sum and neighborhood intersections
cites work: Note on Hamilton Circuits
full work available at URL: 0012-365x(92)00049-w
OpenAlex ID: W2113707442
description: scientific article; zbMATH DE number 500605