Hamiltonian circuits and paths in subset graphs with circular adjacency (Q1313856): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q704847 |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Igor Edm. Zverovich / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Gray codes in graphs of subsets / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(93)90292-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1996705597 / rank | |||
Normal rank |
Latest revision as of 12:05, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hamiltonian circuits and paths in subset graphs with circular adjacency |
scientific article |
Statements
Hamiltonian circuits and paths in subset graphs with circular adjacency (English)
0 references
23 January 1996
0 references
Let \(G(n,k)\) be the graph whose vertex set is the set of all binary \(n\)- tuples with exactly \(k\) 1's and for which an edge exists between two such vertices if and only if one vertex can be transformed into the other by the interchange of two adjacent coordinate values (with the first and last coordinates considered adjacent). The following results are obtained. Theorem 1. A Hamiltonian circuit exists for \(G(n,k)\) if and only if the following conditions hold: (a) both \(n\) and \(k\) are even, and (b) \(n \geq 7\) and \(k = 2\) or \(n - 2\). Theorem 2. The graph \(G(n,k)\) has a Hamiltonian path if and only if \(n\) and \(k\) are not both even.
0 references
Gray codes
0 references
Hamiltonian circuit
0 references
Hamiltonian path
0 references