5
$\begingroup$

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

Later, we found tens of counterexamples on more than 30 vertices and believe there are infinitely many counterexamples.

Define $K_{x_1,x_2,...x_n}$ to the complete multipartite digraph with partitions $x_i$ and every edge is oriented in both directions. Let $L=\max x_i$.

Conjecture 1: as $n,L$ vary, there are infinitely many counterexamples

Q1 Does this give infinitely many counterexamples?

sagemath code for $K_{1,1,2,5}$:

G1=graphs.CompleteMultipartiteGraph((1,1,2,5)).to_directed()
sage: print G1.edges(False)
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 0), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 0), (2, 1), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 0), (3, 1), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 0), (4, 1), (4, 2), (4, 3), (5, 0), (5, 1), (5, 2), (5, 3), (6, 0), (6, 1), (6, 2), (6, 3), (7, 0), (7, 1), (7, 2), (7, 3), (8, 0), (8, 1), (8, 2), (8, 3)]

For counterexample on 15 vertices take $x_i=(1, 1, 1, 2, 2, 8)$.

Added The suggested counterexamples are wrong and were the result of a program bug.

enter image description here

$\endgroup$
1
  • $\begingroup$ The suggested counterexamples are wrong and were the result of a program bug. $\endgroup$
    – joro
    Aug 17, 2020 at 17:29

1 Answer 1

4
$\begingroup$

These examples are symmetric digraphs, i.e. graphs. For graphs, the Nash-Williams conjecture just becomes Chvatal's theorem (If $G$ is a graph on $n\geq 3$ vertices with degree sequence $d_1\leq d_2\leq \dots\leq d_n$ and for all $1\leq i<n/2$, $d_i\geq i+1$ or $d_{n-i}\geq n-i$, then $G$ has a Hamiltonian cycle). In other words, these examples can't be counterexamples to Nash-Williams conjecture.

Of course there is no Hamiltonian cycle in these examples since there is an independent set larger than $n/2$, but Nash-Williams condition is not met. Look at the example $K_{1,1,1,1,5}$ for instance; both degree sequences are $[4,4,4,4,4,8,8,8,8]$, but $d_4=4$ and $d_{9-4}=d_5=4$.

$\endgroup$
5
  • 1
    $\begingroup$ Thanks. I had typo in the first graph. According to my computations, the following non-hamiltonian digraphs satisfy nash's hypothesis, would you please verify them: (1, 1, 1, 3, 7) and (1, 1, 1, 2, 2, 8) $\endgroup$
    – joro
    Aug 16, 2020 at 5:48
  • 1
    $\begingroup$ Again, my answer explains that these can’t be counterexamples. All of your examples are subgraphs of the non-Hamiltonian graph $K_{1,1,\dots,1,(n+1)/2}$. In this graph $d_{(n-1)/2}=(n-1)/2$ and $d_{(n+1)/2}=(n-1)/2$ so Nash-Williams doesn’t hold. Since you aren’t providing the degree sequence I can’t tell why you think it does. $\endgroup$
    – Louis D
    Aug 16, 2020 at 11:04
  • 1
    $\begingroup$ Thanks again! I might have a bug in my program, trying to debug it and write then. $\endgroup$
    – joro
    Aug 17, 2020 at 12:49
  • 1
    $\begingroup$ This question is entirely wrong because of program bug (very likely in upstream sage). Sorry about wasting your time. Probably will delete the question. $\endgroup$
    – joro
    Aug 17, 2020 at 15:59
  • 1
    $\begingroup$ @joro: IIRC you can't delete a question that has an answer with positive score (nor should you!). $\endgroup$ Aug 17, 2020 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.