Enumeration of Hamiltonian Cycles on a Complete Graph using ECO method

Abstract

ECO is a method for enumerating classes of combinatorial objects based on recursive constructions of such classes. A construction for a class of Hamiltonian cycles in a complete graph consisting of n nodes is constructed based on ECO method. Here, a Hamiltonian cycle is represented as a permutation cycle of length n whose permutation and its corresponding inverse permutation are not distinguished. Later, this construction is translated into a succession rule. The final goal of this paper is to determine the generating function of Hamiltonian cycles and it is achieved by making use of the ordinary generating function of a permutation class and the exponential generating function of the infinite sequences of 1s.

Keywords: ECO method, Hamiltonian cycle, cycle permutation, generating function, succession rule.