Graphs preserved under the Hamiltonian path operator

Question

Given a graph $G$ with vertex set $V$, let $HP(G)$ be the graph on $V$ where there's an edge from $u$ to $v$ if and only if there's a Hamiltonian path in $G$ from $u$ to $v$. (I believe this is called the Hamiltonian path operator, but all references I can find to it are from a computational perspective.)

Anyway, here's my question: for which graphs $G$ is $HP(G) \simeq G$? There are some obvious examples (complete graphs, their complements, n-cycles, and $K_{n,n}$s), and at least one less-obvious example ($K_{2,1,1}$, or a square with one diagonal). The latter is certainly more interesting, because the isomorphism between $HP(G)$ and $G$ doesn't just map each vertex to itself. Are there others like it, or any obvious ones I missed? Even better, can we completely classify these graphs?

Answer 1

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 $G\cong 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:$\phantom{wasn't readable cause of 1 char}$

Lemma 2 Let $1 \le k\le n-1$ If $v_{i}\leftrightarrow v_{i+k}$ for some $i\equiv \alpha\pmod{2}$, then this is true for all $i\equiv \alpha\pmod{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_{i\pm 1}\leftrightarrow v_{j\pm 1}$ in $HP(G)$

Lemma 3 If there are $a\neq b\in \mathbb{Z}/n\mathbb{Z}$ so that $\forall i, v_{i}\leftrightarrow v_{i+a}$ and $v_i\leftrightarrow v_{i+b}$ then $G$ is the complete graph.

Corollary You can prove that if $n=|V(G)|$ is odd and $G\cong 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$.

Answer 2

Another one like your K4-e example is an 8-cycle plus two out of its four long diagonals (equivalently, subdivide four of the six edges of K4 so that the two unsubdivided edges are non-adjacent).

Answer 3

Two more large families (one of which includes both David's example and $K_{2,1,1}$) are:

• A 4n-cycle plus n of the 2n long diagonals (every other one).

• A 2n-cycle with an n-cycle inscribed in it along the odd vertices.