THUẬT TOÁN ĐA THỨC XÁC ĐỊNH CHU TRÌNH HAMILTON TRONG LỚP ĐỒ THỊ σ2 ≥ n-1

Tóm tắt

Cho trước một đồ thị đơn vô hướng với n đỉnh, ta kí hiệu σ₂ là tổng bậc bé nhất của các cặp đỉnh không kề nhau trong G. Trong [1], các tác giả đã khảo sát đồ thị n đỉnh thỏa mãn điều kiện d(x)+d(y)=n-1  cho mọi cặp đỉnh không kề nhau x và y và chứng minh rằng đồ thị có chu trình Hamilton (chu trình đi qua tất cả các đỉnh của đồ thị) khi và chỉ khi n lẻ và 2<α< ^n-1/2 ở đó α là chỉ số ổn định trong (số lớn nhất các đỉnh đôi một không kề nhau). Trong bài báo này chúng tôi khảo sát các lớp đồ thị rộng hơn là các lớp đồ thị thỏa mãn σ₂ ≥ n-1 . Chúng tôi chứng minh rằng khi đồ thị thỏa mãn σ₂ ≥ n-1 thì nó có chu trình Hamilton trừ một số lớp đồ thị đặc biệt có thể nhận biết trong thời gian đa thức