Có vô số ví dụ phản bác cho phỏng đoán của Nash-Williams về hamiltonicity?
Câu hỏi từ năm 2013 đưa ra một ví dụ ngược lại với phỏng đoán của Nash-Williams về tính hamiltonicity của các đồ thị dày đặc.
Sau đó, chúng tôi đã tìm thấy hàng chục đối số trên hơn 30 đỉnh và tin rằng có vô số đối tượng.
Định nghĩa $K_{x_1,x_2,...x_n}$ đến đồ thị đa phân hoàn chỉnh với các phân vùng $x_i$và mọi cạnh đều được định hướng theo cả hai hướng. Để cho$L=\max x_i$.
Phỏng đoán 1: như $n,L$ khác nhau, có vô số ví dụ
Q1 Điều này có đưa ra vô số ví dụ không?
mã hiền triết cho $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)]
Đối với mẫu đối số trên 15 đỉnh lấy $x_i=(1, 1, 1, 2, 2, 8)$.
Đã thêm Các ví dụ được đề xuất là sai và là kết quả của lỗi chương trình.
Trả lời
Những ví dụ này là đồ thị đối xứng, tức là đồ thị. Đối với đồ thị, phỏng đoán Nash-Williams chỉ trở thành định lý Chvatal (Nếu$G$ là một đồ thị trên $n\geq 3$ đỉnh với trình tự mức độ $d_1\leq d_2\leq \dots\leq d_n$ và cho tất cả $1\leq i<n/2$, $d_i\geq i+1$ hoặc là $d_{n-i}\geq n-i$, sau đó $G$có chu trình Hamilton). Nói cách khác, những ví dụ này không thể là ví dụ đối lập với phỏng đoán của Nash-Williams.
Tất nhiên không có chu trình Hamilton trong các ví dụ này vì có một tập độc lập lớn hơn $n/2$, nhưng điều kiện Nash-Williams không được đáp ứng. Nhìn vào ví dụ$K_{1,1,1,1,5}$ví dụ; cả hai trình tự mức độ là$[4,4,4,4,4,8,8,8,8]$, nhưng $d_4=4$ và $d_{9-4}=d_5=4$.