Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 325.05114
Autor: Bollobás, Béla; Erdös, Paul
Title: Alternating Hamiltonian cycles. (In English)
Source: Israel J. Math. 23, 126-131 (1976).
Review: For natural numbers n and d, let Kn(\Deltac \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 \Deltac 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 = Kn(\Deltac \leq d) contains an alternating hamiltonian cycle. In fact, it is stated that if 69d < n, then every G = Kn(\Deltac \leq d) contains alternating cycles of length \ell for every \ell, 3 \leq \ell \leq n. An analogous result is obtained as follows. Let \chiv denote the number of colors appearing among the edges containing the vertex v, and let Kn(\chiv \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 Kn(\chiv \geq (7/8)n) contains an alternating hamiltonian cycle. Several related results and conjectures are also presented.
Reviewer: S.F.Kapoor
Classif.: * 05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag