# Is Hamiltonian path NP-hard on graphs of diameter 2?

Let $G$ be a graph of diameter 2 ($\forall u,v\in V: d(u,v)\leq2$).

Can we decide if $G$ has Hamiltonian path in poly time? What about digraphs?

Perhaps some motivation is in place:

the question arises from Dirac's theorem which states that if $\forall v\in V:d(v)\geq \frac{n}{2}$ then the graph is Hamiltonian, as well as it's generalizations (the Ghouila-Houri theorem and the result from Bang-Jensen and Gutin's book).

I've shown here that these degree requirements imply that the graph has diameter 2, and was wondering if such graphs can be decided without the degree requirements (strong gut feeling: No).

• What do you think? What have you tried? What research have you done? Have you tried drawing some example graphs and trying to see if you can come up with an algorithm that will work for them? What can you say about the general form of a graph with diameter $\le 2$? – D.W. Apr 28 '14 at 3:30
• @D.W. - the question arises from Dirac's theorem which states that if $\forall v\in V:d(v)\geq \frac{n}{2}$ then the graph is Hamiltonian, as well as it's generalizations (the Ghouila-Houri theorem and the result from Bang-Jensen and Gutin's book). I've shown here that these degree requirements imply that the graph has diameter 2, and was wondering if such graphs can be decided without the degree requirements (strong gut feeling: No). – R B Apr 28 '14 at 8:39
• What happens if you add a universal vertex to the graph with a pendant vertex? What is the diameter of this graph? When does this graph have a hamiltonian path? – Pål GD Apr 28 '14 at 10:19

• We don't need to reason about the number of edges --- the comment of Pål GD on the question shows that Hamiltonian Path is still NP-hard on graphs of diameter $2$. Given any graph $G$, add a vertex $v$ that is connected to every vertex of $G$, and then add another vertex $u$ that is connected only to $v$. The new graph has diameter $2$. Any Hamiltonian path in the new graph must be of this form: Start at $u$, pass through $v$, and then trace a Hamiltonian path in the original graph $G$. So finding a HP in the new, diameter-2 graph would give an HP in the original, general graph $G$. – usul Jun 2 '14 at 23:23