×

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
Citations:
Zbl 0191.22701
PDF BibTeX XML Cite
Full Text: DOI