Alternating Hamiltonian cycles
type: Item
instance of: scholarly article
title: Alternating Hamiltonian cycles
zbMATH Open document ID: 0325.05114
DOI: 10.1007/BF02756791
author: Béla Bollobás
author: P. Erdős
published in: Israel Journal of Mathematics
publication date: 1976-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 3508538
reviewed by: S. F. Kapoor
MaRDI profile type: Publication
cites work: Q4773725
cites work: On maximal paths and circuits of graphs
full work available at URL: https://doi.org/10.1007/bf02756791
OpenAlex ID: W2084387411
description: scientific article; zbMATH DE number 3508538