Infiniti controesempi alla congettura di Nash-Williams sull'hamiltonicità?

Question

La domanda del 2013 fornisce un controesempio alla congettura di Nash-Williams sull'hamiltonicità dei digrammi densi.

Successivamente, abbiamo trovato decine di controesempi su più di 30 vertici e crediamo che ci siano infiniti controesempi.

Definire $K_{x_1,x_2,...x_n}$ al digrafo multipartito completo con partizioni $x_i$e ogni bordo è orientato in entrambe le direzioni. Permettere$L=\max x_i$.

Congettura 1: as $n,L$ variare, ci sono infiniti controesempi

Q1 Questo fornisce infiniti controesempi?

codice sagemath per $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)]

Per controesempio su 15 vertici, prendere $x_i=(1, 1, 1, 2, 2, 8)$.

Aggiunto I controesempi suggeriti sono sbagliati e sono stati il ​​risultato di un bug del programma.

Answer 1

Questi esempi sono digrafi simmetrici, cioè grafici. Per i grafici, la congettura di Nash-Williams diventa semplicemente il teorema di Chvatal (If$G$ è un grafico su $n\geq 3$ vertici con sequenza di gradi $d_1\leq d_2\leq \dots\leq d_n$ e per tutti $1\leq i<n/2$, $d_i\geq i+1$ o $d_{n-i}\geq n-i$, poi $G$ha un ciclo hamiltoniano). In altre parole, questi esempi non possono essere controesempi alla congettura di Nash-Williams.

Ovviamente non esiste un ciclo hamiltoniano in questi esempi poiché esiste un insieme indipendente maggiore di $n/2$, ma la condizione di Nash-Williams non è soddisfatta. Guarda l'esempio$K_{1,1,1,1,5}$per esempio; entrambe le sequenze di laurea sono$[4,4,4,4,4,8,8,8,8]$, ma $d_4=4$ e $d_{9-4}=d_5=4$.