# zbMATH — the first resource for mathematics

The number of 2-edge-colored complete graphs with unique Hamiltonian alternating cycle. (English) Zbl 1017.05068
Authors’ abstract: “Let $$G$$ be a 2-edge-colored complete graph of even order $$n$$. A cycle of $$G$$ is alternating if any two successive edges differ in color. We prove that there is a one-to-one correspondence between the set of bipartite tournaments of order $$n$$ admitting a unique Hamiltonian cycle and the set of 2-edge-colored complete graphs of order $$n$$ admitting a unique alternating Hamiltonian cycle.”
Since $$w_n$$, the number of bipartite tournaments on $$n$$ vertices with a unique Hamiltonian cycle, is defined by the recursive formula $$w_n= 4w_{n-2}+ w_{n-2}$$ for $$n\geq 8$$, with $$w_4= w_6= 1$$, the same formula counts the number of non-isomorphic 2-edge-colored complete graphs of order $$n$$ admitting a unique alternating Hamiltonian cycle.
Reviewer’s remark: Two sources are given for the above recursive formula: [M. Manoussakis and Y. Manoussakis, The number of bipartite tournaments with a unique given factor, J. Graph Theory 13, 359-368 (1989)] and [J. W. Moon, Topics on tournaments (Holt, Rinehart and Winston, New York, etc.) (1968; Zbl 0191.22701)] but it is not made clear whether the formula appears in both sources.

##### MSC:
 05C45 Eulerian and Hamiltonian graphs 05C15 Coloring of graphs and hypergraphs 05C30 Enumeration in graph theory
##### Keywords:
alternating cycles; Hamiltonian cycles; complete graphs
Zbl 0191.22701
Full Text: