Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các điều kiện cần và đủ để đồ thị tuần hoàn là antistrong, weakly-antistrong và anti-Eulerian
Tóm tắt
Một đường đi phản hướng trong một đồ thị hướng (digraph) là một đường đi (một hành trình không lặp lại các cung) trong đó các cung liên tiếp có hướng ngược nhau. Các đường đi phản hướng tiến (forward antidirected trails) là những đường đi phản hướng đặc biệt bắt đầu và kết thúc với các cung tiến (forward arcs). Một đồ thị hướng D chứa một đường đi phản hướng (x, y)-tiến với mọi lựa chọn của $$x,y\in V(D)$$ được gọi là antistrong. Một đường đi phản hướng bắt đầu với một cung tiến và kết thúc bằng một cung lùi được gọi là đường đi phản hướng tiến-lùi (forward-backward antidirected trail). Đối với bất kỳ $$x,y\in V(D)$$, nếu đồ thị hướng D có một đường đi phản hướng (x, y)-tiến hoặc một đường đi phản hướng tiến-lùi (x, y)-tiến, thì D được coi là weakly-antistrong. Một đồ thị hướng được gọi là anti-Eulerian nếu nó cho phép một đường đi Euler đóng phản hướng. Gọi $$BC(Z_n, C)$$ là một đồ thị Bi-Circulant với $$n\ge 3$$ và $$C=\{j_1, j_2, \ldots , j_{l}\}$$, với $$l\ge 2$$. Bài báo này chỉ ra rằng số lượng thành phần liên thông của $$BC(Z_n, C)$$ bằng $$gcd(j_1-j_l, \ldots , j_{l-1}-j_{l}, n)$$. Dựa trên kết quả này, các điều kiện cần và đủ được đưa ra để xác định xem một đồ thị tuần hoàn có phải là antistrong, weakly-antistrong hay anti-Eulerian hay không.
Từ khóa
#đồ thị hướng #đường đi phản hướng #antistrong #weakly-antistrong #anti-Eulerian #đồ thị tuần hoànTài liệu tham khảo
Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, London (2009)
Bang-Jensen, J., Bessy, S., Jackson, B., Kriesell, M.: Antistrong digraphs. J. Combin. Theory Ser. B 122, 68–90 (2017)
Chartrand, G., Gavlas, H., Schultz, M., Wall, C.: Anticonnected digraphs. Util. Math. 51, 41–54 (1997)
Dobson, E.: Connectivity of circulant digraphs. J. Graph Theory 10, 9–14 (1986)
Dobson, E.: On isomorphisms of circulant digraphs of bounded degree. Disc. Math. 308, 6047–6055 (2008)
Grünbaum, B.: Antidirected Hamiltonian paths in tournaments. J. Combin. Theory Ser. B 11, 249–257 (1971)
Hu, Y., Wei, Y.: Rainbow antistrong connection in tournaments. Graphs Comb. 37, 167–181 (2021)
Liang, X., Meng, J., Zhang, Z.: Super-connectivity and hyper-connectivity of vertex transitive bipartite graphs. Graphs Comb. 23, 309–314 (2007)
Lu, Z.: On the automorphism groups of bi-cayley graphs. Acta. Sci. Nat. Univ. Pekinensis. 39 (2003)
Meng, J., Huang, Q.: Isomorphisms of circulant diagaphs. Appl. Math. A J. Chin. Univ. 9, 405–409 (1994)
Park, J.H., Chwa, K.Y.: Recursive circulant : a new topology for multicomputers networks. Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN). IEEE. 73-80 (1994)
Xu, M.: Introduction of Finite Groups II. Science Press, Beijing (1999)
Yuan, L., Meng, J., Sabir, E.: The antistrong property for special digraph families. Graphs Comb. 37, 2511–2519 (2021)
Zhang, B., Wu, B.: Anti-Eulerian digraphs. Appl. Math. Comput. 411, 126513 (2021)