Chia sẻ bài báo qua Email 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
Thông tin bài báo
Ngày nhận bài: 17/12/24 Ngày hoàn thiện: 06/03/25 Ngày đăng: 07/03/25Các tác giả
1. Lê Như Hiền
, Trường Đại học Công nghiệp Hà Nội2. Mai Thanh Hồng, Trường Đại học Công nghiệp Hà Nội
3. Vũ Thị Tuyết Mai, Trường Đại học Công nghiệp Hà Nội
4. Chu Thị Quyên, Trường Đại học Công nghiệp Hà Nội
5. Lê Xuân Hùng, Trường Đại học Công nghiệp Hà Nội
Tóm tắt
Đồ 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.
Từ khóa
Toàn văn:
PDFTài liệu tham khảo
[1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications, Springer, New York, 2001.
[2] C. Thomassen, “Disjoint cycles in digraphs,” Combinatorica, vol. 3, pp. 393 – 396, 1983.
[3] M. A. Henning and A. Yeo, “Vertex disjoint cycles of different length in digraphs,” SIAM J. Discrete Math., vol. 26, pp. 687 – 694, 2012.
[4] N. Lichiardopol, “Proof of a conjecture of Henning and Yeo on vertex-disjoint directed cycles,” SIAM J. Discrete Math., vol. 28, pp. 1618 – 1627, 2014.
[5] D. T. Ngo, “Tournaments and bipartite tournaments without vertex disjoint cycles of different lengths,” SIAM J. Discrete Math., vol. 35, no. 1, pp. 485 – 494, 2021.
[6] X. H. Le, D. H. Do, and D. T. Ngo, “Vertex-disjoint cycles of different lengths in multipartite tournaments,” Discrete Math., vol. 345, 2022, Art. no. 112819.
[7] X. H. Le and D. T. Ngo, “Vertex-Disjoint Cycles of Different Lengths in Local Tournaments,” Graphs and Combinatorics, vol. 39, no. 5, 2023, Art. no. 92.
[8] J. Bang-Jensen and F. Havet, “Tournaments and semicomplete digraphs,” in Classes of Directed Graphs, J. Bang-Jensen and F. Havet, eds., Springer, New York, 2018, pp. 35 – 124.
DOI: https://doi.org/10.34238/tnu-jst.11722
Các bài báo tham chiếu
- Hiện tại không có bài báo tham chiếu