1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.