THUẬT TOÁN ĐA THỨC XÁC ĐỊNH CHU TRÌNH HAMILTON TRONG LỚP ĐỒ THỊ

Abstract

Cho trước một đồ thị đơn vô hướng với  đỉ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 .

Trong [1], các tác giả đã khảo sát đồ thị đỉnh thỏa mãn điều kiện  cho mọi cặp đỉnh không kề nhau và 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  lẻ và   , ở đó  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 . Chúng tôi chứng minh rằng khi đồ thị thỏa mãn  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.