Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

3 Answers

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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