6

2

Maybe I am missing something, but found potential counterexample to a conjecture of Nash-Williams.

According to HAMILTONIAN DEGREE SEQUENCES IN DIGRAPHS

The outdegree and indegree sequences of digraph $G$ are $d_1^+ \le \cdots \le d_n^+$ and $d_1^- \le \cdots \le d_n^-$. Note that the terms $d_i^+$ and $d_i^-$ do not necessarily corresponds to the degree of the same vertex of $G$.

Conjecture 1 (Nash-Williams). Suppose that $G$ is a strongly connected digraph on $n \ge 3$ vertices such that for all $i < n/2$

(i) $d_i^+ \ge i + 1$ or $d_{n-i}^- \ge n - i$,

(ii) $d_i^- \ge i + 1$ or $d_{n-i}^+ \ge n - i$,

Then $G$ contains a Hamilton cycle.

The potential counterexample is $G$ on $6$ vertices with edges:

[(0, 3), (0, 5), (1, 4), (1, 5), (2, 3), (2, 4), (3, 0), (3, 2), (3, 4), (3, 5), (4, 0), (4, 1), (4, 3), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4)]

$G$ is strongly connected and by inspection the degree sequences satisfy the hypotheses for $i \in [1,2]$ (both degree sequences are $[2, 2, 2, 4, 4, 4]$).

Nonhamitlonicity was shown using exhaustive search, sage 5.6 and Max Alekseyev's hamiltonian cycle counting pari program.

Is this really a counterexample the the conjecture of Nash-Williams?

Drawing of $G$:

flag
1 
I cannot see anything wrong with your reasoning, so I'll say "yes, it is a counterexample" – gordon-royle Mar 12 at 7:25
From what I can see it's a counter-example. Though I would go back and check the statement of the conjecture as given by Nash-Williams (the source of which doesn't seem to be online). The check of non-Hamiltonicity is pretty easy to do by hand: a Hamiltonian cycle has to alternate between vertices in {0,1,2} and {3,4,5} since there are no edges among {0,1,2}. Now it's clear that 1 has to fall between 4 and 5, so the two possibilities are 3,$x$,5,1,4,$y$ and 3,$x$,4,1,5,$y$ and they can both be ruled out. – Hugh Thomas Mar 14 at 15:15

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.