Bijections Between Smirnov Words and Hamiltonian Cycles in Complete Multipartite Graphs
Abstract
We establish a bijective correspondence between Smirnov words with balanced letter multiplicities and Hamiltonian paths in complete $m$-partite graphs $K_{n,n,\ldots,n}$. This bijection allows us to derive closed inclusion-exclusion formulas for the number of Hamiltonian cycles in such graphs. We further extend the enumeration to the generalized nonuniform case $K_{n_1,n_2,\ldots,n_m}$. We also provide an asymptotic analysis based on Stirling's approximation, which yields compact factorial expressions and logarithmic expansions describing the growth of the number of Hamiltonian cycles in the considered graphs. Our approach unifies the combinatorial study of adjacency-constrained words and the enumeration of Hamiltonian cycles within a single analytical framework.