# Hamiltonian graph join

Assume a graph $$(V,E)$$ with $$n$$ vertices and degree sequence $$d_1 \geq d_2 \geq \dots \geq d_n$$.

The purpose of this question is to understand when the graph join $$G^{(k)}$$ (defined as the union of $$k$$ copies of $$G$$ with all the edges between vertices that belong to different copies of $$G$$ present) is Hamiltonian.

$$G^{(k)}$$ has $$kn$$ vertices with degree sequence:

$$(d_1 + (k-1)n, \dots ,d_1 + (k-1)n, d_2 + (k-1)n, \dots, d_2 + (k-1)n, \dots, d_n + (k-1)n, \dots, d_n + (k-1)n)$$ (each $$d_i$$ is repeated $$k$$ times).

Using Dirac's theorem, if

$$d_i + (k-1)n \geq \frac{kn}{2}, \, i =1,2,\dots,n \iff d_i \geq \frac{n(2-k)}{2}, \, i =1,2,\dots,n$$

then $$G^{(k)}$$ is Hamiltonian. But $$k \geq 2$$, so the inequality is always true.

There's probably a mistake somewhere, 'cause this would imply that every graph join is Hamiltonian.

Isn't it Hamiltonian? Let $$v_{i,j}$$ be the copy of vertex $$i$$ in copy $$j$$ of $$G$$. Then we have the path$$v_{1,1},v_{1,2},\dots, v_{1,k},v_{2,1},v_{2,2},\dots,v_{2,k}\dots,v_{n,k},v_{1,1}$$ We must have either $$n>1$$ or $$k>2$$ so that $$G^{(k)}$$ has at least $$3$$ vertices for Dirac's theorem to apply. In the case where $$n=1$$ and $$k=2$$, $$G^(2)$$ has a single edge, so is not Hamiltonian.