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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$ Commented Aug 17, 2020 at 16:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .