One criterion of existence of a Hamiltonian cycle
type: Item
instance of: scholarly article
title: One criterion of existence of a Hamiltonian cycle
zbMATH Open document ID: 0894.05039
DOI: 10.1023/A:1009993312051
author: Anatoly D. Plotnikov
published in: Reliable Computing
publication date: 1998-08-31T00:00:00Z
review text: Let \(G=(X, A)\) be a finite connected graph. Further, let \(X_1\subset X\) be some independent set of vertices of the graph \(G.\) Denote by \(P(X_1)\) set of all paths connecting vertices of the set \(X_1.\) Call the set of vertices \(U(P(X_1))\subset X\) \((U(P(X_1))\cap X_1=\varnothing)\) separating for the vertices of the set \(X_1\), if removing these vertices from the graph \(G\) along with their incident edges cuts each path of \(P(X_1).\) A separating set \(\overline{U} (P(X_1))\) is called minimum if \(\text{Card}(\overline{U} (P(X_1)))\leq \text{Card} (U(P(X_1)))\), where \(U(P(X_1))\) is any separating set of vertices for the set \(X_1.\) The main result of this note is the following theorem: A finite graph \(G=(X, A)\) is Hamiltonian if and only if \(\text{Card} (X_1)\leq \text{Card} (\overline{U} (P(X_1)))\) for any independent set of vertices \(X_1\subset X\).
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1160469
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: independent set
reviewed by: Stanislav Jendroľ
MaRDI profile type: Publication
full work available at URL: a:1009993312051
OpenAlex ID: W205003709
description: scientific article; zbMATH DE number 1160469