The number of 2-edge-colored complete graphs with unique Hamiltonian alternating cycle. (English) Zbl 1017.05068

Benkouar, A.; Manoussakis, Y.; Saad, R.

Discrete Math. 263, No. 1-3, 1-10 (2003).

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.

Reviewer: Timothy R.Walsh (Montréal)

MSC:

05C45	Eulerian and Hamiltonian graphs
05C15	Coloring of graphs and hypergraphs
05C30	Enumeration in graph theory

Keywords:

alternating cycles; Hamiltonian cycles; complete graphs

Citations:

Zbl 0191.22701