Alternating Hamiltonian cycles (Q1225065): Difference between revisions

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.