5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – D.W. Apr 28 '14 at 3:30
  • $\begingroup$ @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). $\endgroup$ – R B Apr 28 '14 at 8:39
  • 7
    $\begingroup$ 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? $\endgroup$ – Pål GD Apr 28 '14 at 10:19
2
$\begingroup$

Assuming you are talking about directed graphs, the work of Füredi et al. [1] shows that such graphs of n vertices and diameter 2 have at least ~n log (n) edges, or an average degree of ~log(n). I am aware of no subsequent result tightening this result, and the authors themselves suggest that they think this result is tight; this is quite far from the known sufficient conditions for Hamiltonian paths, which are based on a roughly linear vertex degree.

As a result, this appears to be an open and difficult problem that would require some significant research for a solution.

[1] Füredi, Zoltán, et al. "Minimal oriented graphs of diameter 2." Graphs and Combinatorics 14.4 (1998): 345-350.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – usul Jun 2 '14 at 23:23

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.