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?

  • $\begingroup$ Are you only interested in finite graphs? In that case I might have a approach. $\endgroup$ – Gjergji Zaimi Jan 3 '10 at 22:23
  • $\begingroup$ 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. $\endgroup$ – Harrison Brown Jan 3 '10 at 22:40
  • $\begingroup$ 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?) $\endgroup$ – 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:$\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$.

  • $\begingroup$ Do you mean the only complete k-partite graphs? David Eppstein's example doesn't have any of the above forms. $\endgroup$ – Harrison Brown Jan 3 '10 at 23:08
  • $\begingroup$ I assume so, since every graph is k-partite for big enough k. $\endgroup$ – Jonah Ostroff Jan 3 '10 at 23:27
  • $\begingroup$ Sorry, I edited once more. $\endgroup$ – 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).

  • $\begingroup$ I got scooped! Shouldn't have spent fifteen minutes trying to figure out if that graph had a name... $\endgroup$ – 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.


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.