# Graphs preserved under the Hamiltonian path operator

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?

-
Are you only interested in finite graphs? In that case I might have a approach. – Gjergji Zaimi Jan 3 '10 at 22:23
Can we even prove that every such graph either has no edges or is Hamiltonian? I think I might have an approach to this, but it seems overly complicated and it's likely my logic is wrong, so I don't want to spend a lot of time if someone has an easier solution. – Harrison Brown Jan 3 '10 at 22:40
At this point, I don't think we have any examples which don't lie in some well-understood larger family of examples. So this seems like a good time to try proving that the graphs seen so far are all such graphs, and for this I've opened up a bounty. Any takers? (Or, I suppose, any more exceptional examples?) – Jonah Ostroff Jan 11 '10 at 22:03

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:

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$.

-
Do you mean the only complete k-partite graphs? David Eppstein's example doesn't have any of the above forms. – Harrison Brown Jan 3 '10 at 23:08
I assume so, since every graph is k-partite for big enough k. – Jonah Ostroff Jan 3 '10 at 23:27
Sorry, I edited once more. – Gjergji Zaimi Jan 3 '10 at 23:29

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).

-
I got scooped! Shouldn't have spent fifteen minutes trying to figure out if that graph had a name... – Harrison Brown Jan 3 '10 at 22:18

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.

-