Bijections Between Smirnov Words and Hamiltonian Cycles in Complete Multipartite Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915587003777024 |
|---|---|
| author | Mehiri, El-Mehdi |
| author_facet | Mehiri, El-Mehdi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26597 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bijections Between Smirnov Words and Hamiltonian Cycles in Complete Multipartite Graphs Mehiri, El-Mehdi Combinatorics Discrete Mathematics 05A05, 05C45, 05A15, 05C30 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. |
| title | Bijections Between Smirnov Words and Hamiltonian Cycles in Complete Multipartite Graphs |
| topic | Combinatorics Discrete Mathematics 05A05, 05C45, 05A15, 05C30 |
| url | https://arxiv.org/abs/2510.26597 |