Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Hai điều kiện đủ cho đồ thị 2 liên thông có số kết nối đúng bằng 2
Tóm tắt
Số kết nối đúng của một đồ thị G, ký hiệu là pc(G), là số màu tối thiểu cần thiết để tô màu các cạnh của G sao cho mỗi cặp đỉnh phân biệt của G được kết nối bởi một đường đi trong đó không có hai cạnh kề nhau của đường đi nào nhận cùng một màu. Một đồ thị liên thông G được gọi là k-PC nếu pc(G) ≤ k. Trong tài liệu, đã chỉ ra rằng mọi đồ thị có 3 cạnh kết nối là 2-PC và mọi đồ thị có 2 cạnh kết nối là 3-PC. Chúng tôi chỉ ra trong bài báo này rằng mọi đồ thị 2 liên thông sao cho mỗi cạnh nằm trong một chu trình có độ dài tối đa là 4 thì là 2-PC, và mọi đồ thị 2 liên thông có bậc tối thiểu ít nhất là 3 sao cho mỗi cạnh nằm trong một chu trình có độ dài tối đa là 6 thì cũng là 2-PC.
Từ khóa
#đồ thị #số kết nối đúng #đồ thị 2 liên thông #tô màu cạnhTài liệu tham khảo
Andrews, E., Laforge, E., Lumduanhom, C., Zhang, P.: On proper-path colorings in graphs. J. Combin. Math. Combin. Comput. 97, 189–207 (2016)
Brause, C., Doan, T.D., Schiermeyer, I.: Minimum degree conditions for the proper connection number of graphs. Graphs Combin. 33(4), 833–843 (2017)
Bondy, J.A., Murty, U.S.R.: Graph Theory, Graduate Texts in Mathematics, vol. 244. Springer, London (2008)
Borozan, V., Fujita, S., Gerek, A., Magnant, C., Manoussakis, Y., Montero, L., Tuza, Z.: Proper connection of graphs. Discrete Math. 312, 2550–2560 (2012)
Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: Rainbow connection in graphs. Math. Bohem. 133, 85–98 (2008)
Chou, W.S., Manoussakis, Y., Megalakaki, O., Spyratos, M., Tuza, Z.: Paths through fixed vertices in edge-colored graphs. Math. Sci. Hum. 127, 49–58 (1994)
Dorninger, D.: On Permutations of Chromosomes, Contributions to General Algebra 5 (Salzburg, 1986), pp. 95–103. Hölder-Pichler-Tempsky, Vienna (1987)
Dorninger, D.: Hamiltonian circuits determining the order of chromosomes. Discrete Appl. Math. 50, 159–168 (1994)
Dorninger, D., Timischl, W.: Geometrical constraints on Bennett’s predictions of chromosome order. Heredity 58, 321–325 (1987)
Gu, R., Li, X.L., Qin, Z.M.: Proper connection number of random graphs. Theor. Comput. Sci. 609, 336–343 (2016)
Huang, F., Li, X.L., Qin, Z.M., Magnant, C.: On two conjectures about the proper connection number of graphs. Discrete Math. 340, 2217–2222 (2017)
Huang, F., Li, X.L., Wang, S.J.: Upper bound of proper connection number of graphs. J. Comb. Optim. 34(1), 165–173 (2017)
Huang, F., Yuan, J.J.: On strong proper connection number of cubic graphs. Discrete Appl. Math. 265, 104–119 (2019)
Li, X.L., Magnant, C.: Properly colored notions of connectivity—a dynamic survey. Theory Appl. Graphs 0(1), 2 (2015). https://doi.org/10.20429/tag.2015.000102
Li, X.L., Wei, M.Q., Yue, J.: Proper connection number and connected dominating sets. Theor. Comput. Sci. 607, 480–487 (2015)
Li, X.L., Magnant, C., Qin, Z.M.: Properly Colored Connectivity of Graphs, Springer Briefs in Mathematics. Springer, Cham (2018)
Li, X.L., Shi, Y.T., Sun, Y.F.: Rainbow connections of graphs: a survey. Graphs Comb. 29, 1–38 (2013)
Li, X.L., Sun, Y.T.: Rainbow Connections of Graphs, Springer Briefs in Mathematics. Springer, New York (2012)
Westbrook, J., Tarjan, R.E.: Maintaining bridge-connected and biconnected components on-line. Algorithmica 7(1–6), 433–464 (1992)