2
$\begingroup$

Question from 2013 gives one counterexample to Nash-Williams's conjecture 1975 about hamiltonicity of dense digraphs.

In the linked answer, @LouisD "reverse engineered" the counterexample and pointed out it is special case in another paper.

We found 2 more digraph counterexamples with directed edges:

g1=[(0, 3), (0, 4), (1, 3), (1, 5), (2, 4), (2, 5), (3, 0), (3, 1), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 5), (5, 0), (5, 2), (5, 3), (5, 4)]
g2=[(0, 2), (0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (2, 0), (2, 4), (3, 0), (3, 1), (3, 4), (3, 5), (4, 0), (4, 3), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4)]
g3=[(0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 5), (2, 0), (2, 1), (2, 4), (2, 5), (3, 1), (3, 5), (4, 1), (4, 2), (5, 0), (5, 1), (5, 2), (5, 3)]

Q1 Are these counterexamples true?

Q2 Can we get infinitely many counterexamples from the small ones?

All three counterexamples are planar.

enter image description here

enter image description here

Improve this question
$\endgroup$
1
  • $\begingroup$ These two examples are closely related in the sense that g3 can be obtained from g2 by deleting the edge (5,4). One can verify that both of these satisfy the Nash-Williams condition and that g2 does not have a Hamiltonian cycle. Thus g3 does not have a Hamiltonian cycle. Since they are both planar, it would probably be helpful to draw them that way so the pictures can be read more clearly. I suggest redrawing the first picture with the vertices in three rows: 5 centered in the first row, 2,0,3,1 in the second row in that order, 4 centered on the bottom. Similarly with the second picture. $\endgroup$
    – Louis D
    Commented Aug 14, 2020 at 18:59

0

Reset to default

You must log in to answer this question.