Note on Hamiltonian Graphs in Abelian $2$-Groups

Kristijan Tabak

Kragujevac Journal of Mathematics, Tome 49 (2025) no. 3, p. 401

Résumé

We analyze a graph $G$ whose vertices are subgroups of $\mathbb{Z}_2^k$ isomorphic to $\mathbb{Z}_2 ×\mathbb{Z}_2.$ Two vertices are joined if their respective subgroups have nontrivial intersection. We prove that such a graph is $6(2^{k-2}-1)$-regular. If a graph is regular, a classical theorem by Ore claims that a graph is Hamiltonian if the degree of any vertex is at least one half of the number of vertices. Using Ore's theorem, we show that $G$ is Hamiltonian for $k \in \{3,4\}.$ Ore's theorem cannot be applied when $k \geq 5$. Nevertheless, we manage to construct a Hamiltonian cycle for $k=5.$ Our construction uses orbits of one $\mathbb{Z}_2^4$ group under an action of an automorphism of order $31.$ It is highly likely that this approach could be generalized for $k>5.$

Détail

Classification : 05C45, 13A50
Keywords: Hamiltonian graph, graph, elementary Abelian group, subgroup, group ring