Alternating Hamiltonian cycles (Q1225065): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q800380 |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: S. F. Kapoor / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4773725 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On maximal paths and circuits of graphs / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf02756791 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2084387411 / rank | |||
Normal rank |
Latest revision as of 10:14, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Alternating Hamiltonian cycles |
scientific article |
Statements
Alternating Hamiltonian cycles (English)
0 references
1976
0 references
For natural numbers \(n\) and \(d\), let \(K_n(\Delta_c \leq d)\) denote a complete graph of order \(n\) whose edges are colored so that no vertex belongs to more than \(d\) edges of the same color, and where \(\Delta_c\) is the maximal degree in the subgraph formed by the edges of color \(c\). D. E. Daykin proved that if \(d=2\) and \(n \geq 6\), then every such graph contains an alternating hamiltonian cycle (i.e. a spanning cycle whose adjacent edges have different colors). The authors have extended this as follows. Theorem: If \(69d <n\), then every \(G=K_n(\Delta_c \leq d)\) contains an alternating hamiltonian cycle. In fact, it is stated that if \(69d<n\), then every \(G=K_n(\Delta_c \leq d)\) contains alternating cycles of length \(\ell\) for every \(\ell\), \(3 \leq \ell \leq n\). An analogous result is obtained as follows. Let \(\chi_v\) denote the number of colors appearing among the edges containing the vertex \(v\), and let \(K_n(\chi_v \geq \lambda)\) denote a complete graph of order \(n\) whose edges are colored so that each vertex is on at least \(\lambda\) edges of different color. Theorem: Every \(K_n(\chi_v \geq (7/8)n)\) contains an alternating hamiltonian cycle. Several related results and conjectures are also presented.
0 references