해밀턴성에 대한 Nash-Williams의 추측에 대해 무한히 많은 반례가 있습니까?

Question

2013 년의 질문 은 조밀 한 digraphs의 hamiltonicity에 대한 Nash-Williams의 추측에 대한 하나의 반례를 제공합니다.

나중에 우리는 30 개 이상의 정점에서 수십 개의 반례를 발견했고 무한히 많은 반례가 있다고 믿습니다.

밝히다 $K_{x_1,x_2,...x_n}$ 파티션이있는 완전한 다자간 digraph에 $x_i$모든 모서리는 양방향으로 향합니다. 허락하다$L=\max x_i$.

추측 1 : as $n,L$ 다양합니다. 무한히 많은 반례가 있습니다.

Q1 이것은 무한히 많은 반례를 제공합니까?

sagemath 코드 $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)]

15 개의 정점에 대한 반례의 경우 $x_i=(1, 1, 1, 2, 2, 8)$.

추가됨 제안 된 반례가 잘못되었으며 프로그램 버그의 결과입니다.

Answer 1

이러한 예는 대칭 digraph, 즉 그래프입니다. 그래프의 경우 Nash-Williams 추측은 Chvatal의 정리가됩니다 (If$G$ 그래프입니다 $n\geq 3$ 차수 시퀀스가있는 정점 $d_1\leq d_2\leq \dots\leq d_n$ 그리고 모두를 위해 $1\leq i<n/2$, $d_i\geq i+1$ 또는 $d_{n-i}\geq n-i$, 다음 $G$해밀턴 사이클이 있음). 즉, 이러한 예는 Nash-Williams의 추측에 반하는 예가 될 수 없습니다.

물론이 예에는 해밀턴 사이클이 없습니다. $n/2$, 그러나 Nash-Williams 조건이 충족되지 않습니다. 예를 봐$K_{1,1,1,1,5}$예를 들어; 두 학위 시퀀스 모두$[4,4,4,4,4,8,8,8,8]$,하지만 $d_4=4$ 과 $d_{9-4}=d_5=4$.