Banyak sekali contoh yang berlawanan dengan dugaan Nash-Williams tentang hamiltonisitas?

Question

Pertanyaan dari tahun 2013 memberikan satu contoh yang berlawanan dengan dugaan Nash-Williams tentang hamiltonisitas digraf padat.

Kemudian, kami menemukan puluhan counterexample di lebih dari 30 simpul dan percaya ada banyak counterexample yang tak terhingga.

Menetapkan $K_{x_1,x_2,...x_n}$ ke digraf multipartit lengkap dengan partisi $x_i$dan setiap sisi diorientasikan ke dua arah. Membiarkan$L=\max x_i$.

Dugaan 1: sebagai $n,L$ bervariasi, ada banyak contoh yang berlawanan

Q1 Apakah ini memberikan banyak contoh balasan?

kode sagemath untuk $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)]

Untuk counterexample pada 15 simpul ambil $x_i=(1, 1, 1, 2, 2, 8)$.

Ditambahkan Contoh kontra yang disarankan salah dan merupakan hasil dari bug program.

Answer 1

Contoh-contoh ini adalah digraf simetris, yaitu grafik. Untuk grafik, dugaan Nash-Williams hanya menjadi teorema Chvatal (If$G$ adalah grafik pada $n\geq 3$ simpul dengan urutan derajat $d_1\leq d_2\leq \dots\leq d_n$ dan untuk semua $1\leq i<n/2$, $d_i\geq i+1$ atau $d_{n-i}\geq n-i$, kemudian $G$memiliki siklus Hamiltonian). Dengan kata lain, contoh-contoh ini tidak dapat menjadi contoh yang berlawanan dengan dugaan Nash-Williams.

Tentu saja tidak ada siklus Hamiltonian dalam contoh ini karena ada himpunan independen yang lebih besar dari $n/2$, namun kondisi Nash-Williams belum terpenuhi. Lihat contohnya$K_{1,1,1,1,5}$contohnya; kedua urutan derajat tersebut$[4,4,4,4,4,8,8,8,8]$, tapi $d_4=4$ dan $d_{9-4}=d_5=4$.