Alternating Hamiltonian cycles. (English) Zbl 0325.05114

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.
Reviewer: S.F.Kapoor


05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] D. E. Daykin,Graphs with cycles having adjacent lines different colours, to appear. · Zbl 0287.05105
[2] P. Erdös and T. Gallai,On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar.10, (1959), 337–356. · Zbl 0090.39401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.