ハミルトン性についてのナッシュウィリアムズの予想に対する無限に多くの反例？

Question

2013年の質問は、密な有向グラフのハミルトン性に関するNash-Williamsの予想に対する1つの反例を示しています。

その後、30を超える頂点で数十の反例が見つかり、無限に多くの反例があると考えています。

定義する $K_{x_1,x_2,...x_n}$ パーティションを含む完全な多分割有向グラフに $x_i$そして、すべてのエッジは両方向に向けられています。しましょう$L=\max x_i$。

予想1：として $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

これらの例は、対称有向グラフ、つまりグラフです。グラフの場合、ナッシュウィリアムズ予想はChvatalの定理になります（$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$ハミルトン閉路を持っています）。言い換えれば、これらの例はナッシュウィリアムズ予想の反例にはなり得ない。

もちろん、これらの例には、より大きい独立集合があるため、ハミルトン閉路はありません。 $n/2$、しかしナッシュウィリアムズ条件が満たされていません。例を見てください$K_{1,1,1,1,5}$例えば; 両方の次数シーケンスは$[4,4,4,4,4,8,8,8,8]$、 だが $d_4=4$ そして $d_{9-4}=d_5=4$。