MỘT SỐ ĐIỀU KIỆN CẦN CHO ĐỒ THỊ GIẢI ĐẤU TÁCH CỰC KHÔNG CÓ CÁC CHU TRÌNH RỜI NHAU VỚI ĐỘ DÀI KHÁC NHAU

Abstract

Đồ thị giải đấu tách cực là đồ thị có hướng D = (V, A) với phân hoạch  sao cho D[K] là đồ thị giải đấu, D[I] không có cung thuộc A và với mọi cặp đỉnh  có đúng một trong các cung (u,v) và (v,u) thuộc A. Ta ký hiệu đồ thị giải đấu tách cực này là . Vấn đề nghiên cứu sự tồn tại các chu trình rời nhau với độ dài khác nhau trong các đồ thị có hướng được bắt đầu nghiên cứu từ năm 1983 bởi C. Thomassen, cho đến nay đã thu được nhiều kết quả sâu sắc và thú vị. Trong bài báo này, chúng tôi sẽ tiếp tục nghiên cứu sự tồn tại các chu trình rời nhau với độ dài khác nhau trong các đồ thị mới, đó là lớp đồ thị giải đấu tách cực liên thông mạnh với bậc ra nhỏ nhất bằng 3. Chúng tôi chứng minh được một số điều kiện cần để lớp đồ thị giải đấu tách cực này không có các chu trình rời nhau với độ dài khác nhau. Các kết quả chính trong bài báo này là những đóng góp bước đầu, quan trọng trong việc tìm ra một đặc trưng cho lớp đồ thị giải đấu tách cực liên thông mạnh với bậc ra nhỏ nhất bằng 3, không có các chu trình rời nhau với độ dài khác nhau.