One criterion of existence of a Hamiltonian cycle (Q1387766): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q582576 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Stanlislav Jendroľ / rank | |||
Normal rank |
Revision as of 11:50, 16 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | One criterion of existence of a Hamiltonian cycle |
scientific article |
Statements
One criterion of existence of a Hamiltonian cycle (English)
0 references
31 August 1998
0 references
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\).
0 references
Hamiltonian cycle
0 references
independent set
0 references