Let G be a simple undirected Graph with the following property : For every pair of vertices $(u,v)$, there is a hamilton path from $u$ to $v$. It is clear that all complete graphs have this property and that the graph must have a hamilton circle to have this property.

A hamilton path is a path visiting EVERY vertex exactly once. A hamilton circle is a circle containing EVERY vertex.

  • Is there a name for such graphs ?

  • Which graphs beside the complete ones have this property (Is there a nice criterion) ?

  • What is the least possible number of edges for a graph with $n$ vertices to have this property ?

  • $\begingroup$ I don't think a Hamiltonian circuit is a necessary consequence, if we mean the same thing when we say that. Consider the graph on a,b,c where a is adjacent to b and c. Eg b-a-c. There is a Hamiltonian path from each vertex to every other vertex, but there is no Hamiltonian circuit on the graph. $\endgroup$ – Tyler Sep 2 '14 at 20:52
  • 1
    $\begingroup$ Ah, okay. That makes this quite a bit more interesting. $\endgroup$ – Tyler Sep 2 '14 at 21:42
  • $\begingroup$ If a graph has the given property, it is $3$-connected. $\endgroup$ – Peter Sep 3 '14 at 17:37

"Which graphs beside the complete ones have this property? (Is there a nice criterion?)"

About the criterion: I can think of every graph that fulfills Pós' theorem, Ore's theorem or Dirac's theorem conditions (because Ore's theorem implies Pós' theorem and Dirac's theorem is conclusion from Ore's theorem).

I will just prove that for Pós theorem (because I can't find it on the Internet so I think it might be hard to find it for you too):

Let $ D_n(G)= \left \{ v\in V: deg_G(v)\leq n \right \}$

Pós' theorem states that: $G$ is a graph with $p$ vertices. If for every $1\leq n < \frac {p-1}{2}$, $D_n(G)<n$ (and for $n=\frac{p-1}{2}$, $D_n(G)\leq n$ if $p$ is odd number) then $G$ is Hamiltonian.

It is easy to prove then that every two vertices in $G$ are ends of a Hamiltonian path (I won't prove the whole theorem here).

Proof: If the theorem is false then there exists counterexamples. Let $H$ be the maximal counterexample to the theorem (that means that adding any new edge to $H$ makes it Hamiltonian). Because adding edges doesn't change Pós condition and makes H Hamiltonian, we proved that every two vertices in H must be ends of some Hamiltonian path. $\square$

  • $\begingroup$ There are two things that are unclear to me : 1) Is H (the maximal counterexample) non-hamiltonian ? Then pos condition cannot hold. 2) Did you consider the case, when the vertices are already neighbours ? Then the edge between these vertices cannot be add. Perhaps your definition of hamiltonian path is different from mine : A hamiltonian path must visit EVERY vertex exactly once. $\endgroup$ – Peter Sep 4 '14 at 12:20
  • $\begingroup$ @Peter: H is the maximal counterexample that fulfills Pós condition and is non-hamiltonian. If the theorem is false it must exist, since we are talking about graphs with finite sets of vertices. 2) I have the same definition of Hamiltonian path and I don't quite understand your question. If two vertices are neigbors it's quite clear that you can't add a new edge between them. But it doesn't mean Hamiltonian path between them doesn't exist - just take a look at a simple cycle $C_n$. You can construct hamiltonian path between every two neigbors. $\endgroup$ – Mateusz Sep 4 '14 at 14:27

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.