co.combinatorics - Graphs preserved under the Hamiltonian path operator

Other examples include $K_{a,1,1,dots,1}$ with $a$ 1's. Together with $K_a$ and $K_{a,a}$ these are the only complete $k$-partite graphs that are fixed points of the "Hamiltonian path operator". But we can do better:

(Edited to include what I have so far)

Lemma 1 If $Gcong HP(G)$ then either $G$ is empty or it has a Hamiltonian cycle.

Proof goes by showing that if $G$ doesn't have a Hamiltonian cycle then it has more edges than $HP(G)$ (Induction)

Let $V(G)=v_1,v_2,dots,v_n$ with $v_i\leftrightarrow v_{i+1}$ (where indices are $pmod{n}$) In fact we can prove:

Lemma 2 Let $1 le kle n-1$ If $v_{i}leftrightarrow v_{i+k}$ for some $iequiv alphapmod{2}$, then this is true for all $iequiv alphapmod{2}$ in particular when $n$ is odd, it is true for all $i$.

The proof is based on the observation that if $v_{i}leftrightarrow v_j$ in $G$ then $v_{ipm 1}leftrightarrow v_{jpm 1}$ in $HP(G)$

Lemma 3 If there are $aneq bin mathbb{Z}/nmathbb{Z}$ so that $forall i, v_{i}leftrightarrow v_{i+a}$ and $v_ileftrightarrow v_{i+b}$ then $G$ is the complete graph.

Corollary You can prove that if $n=|V(G)|$ is odd and $Gcong HP(G)$, then $G$ is the $n$-cycle or the complete graph $K_n$.

When $n$ is even there are non-trivial examples such as the families already mentioned. At least we know that all Graphs that are fixed points of your operator are so that $v_{i}to v_{i+2}$ describes an automorphism of $G$.

• Next gr.group theory - Leech lattice decomposition
• Previous ag.algebraic geometry - Why does finitely presented imply quasi-separated ?