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).
Is Hamiltonian path NP-hard on graphs of diameter 2?
graph theory;graphs;np complete;hamiltonian path