主题
Search

循环边连通性


A 是连通图 G 的一个边割。那么循环边连通性 lambda_c(G)最小循环边割的大小,即最小的边割 A,使得 G-A 有两个连通分量,且每个连通分量都至少包含一个图的环。循环边连通性最早由 Tait (1880) 在 1880 年提出。

注意 Grünbaum (2003, p. 365) 和其他人使用术语“循环 k-连通”(省略了“边”字)来指一个图,它不能通过少于 k 条边的边割被分成两个独立的部分,且每个部分都包含一个环。

循环边割并非对所有图都存在。例如,包含少于两个环的图不可能有两个都包含环的连通分量。没有循环边割的图的例子包括轮图 W_n (Dvorák et al. 2004)。对于不存在循环边割的图,可以认为其 lambda_c=0 (Lou et al. 2001)。

CyclicEdgeConnectivityPetersenGraph

Petersen 图的循环边连通性是 lambda_c(P)=5 (Holton and Sheehan 1993, p. 86; Lou et al. 2001)。这可以从移除五条“径向”边后,留下一个不连通的内部五角星环和外部五边形环这一事实看出。

循环边连通性最常在 snark 图的定义中遇到,snark 图被定义为围长至少为 5 且边色数为 4 的三次循环 4-边连通图。

Birkhoff (1913) 将四色问题简化为循环 5-边连通的多面体图 (Grünbaum 2003, p. 365)。Hunter (1962) 推测这样的图都是 Hamiltonian 图,但这一推测被 162 顶点的三次非 Hamiltonian 162 顶点 Walther 图的发现所驳斥 (Walther 1965, Grünbaum 2003, p. 365)。

Plummer (1972) 表明,平面 5-连通图的循环边连通性最多为 13,而平面 4-连通图的循环边连通性可以是任何大于等于 4 的整数值。Borodin (1989) 表明,平面 5-连通图的最大循环边连通性最多为 11。

一个具有 n 个节点的简单图的循环边连通性满足

 lambda_c(G)<=3(n-3)

n>=6 时,完全图等号成立,即当 n>=6 时,lambda_c(K_n)=3(n-3) (Lou et al. 2001)。


另请参阅

循环边割, 边连通性, 边割, 最小循环边割, Snark

使用 Wolfram|Alpha 探索

参考文献

Birkhoff, G. D. "The Reducibility of Maps." Amer. J. Math 35, 115-128, 1913.Borodin, O. V. "Solution of Kotzig's and Grünbaum's Problems on Separability of a Cycle in Planar Graphs." Mat. Zametki 46, 9-12, 1989.Dvorák, Z.; Kára, J.; Král', D.; and Pangrác, O. "An Algorithm for Cyclic Edge Connectivity of Cubic Graphs." In Algorithm Theory--SWAT 2004 (Ed. T. Hagerup and J. Katajainen). Berlin: Springer, pp. 236-247, 2004.Grünbaum, B. Convex Polytopes, 2nd ed. New York: Springer-Verlag, 2003.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, p. 86, 1993.Hunter, H. F. On Non-Hamiltonian Maps and their Duals. Ph. D. thesis. Troy, NY: Rensselaer Polytechnic Institute, 1962.Lou, D.; Teng, L.; and Wu, S. "A Polynomial Algorithm for Cyclic Edge Connectivity of Cubic Graphs." Austral. J. Combin. 24, 247-259, 2001.Plummer, M. D. "On the Cyclic Connectivity of Planar Graphs." In Graph Theory and Applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972). Berlin: Springer-Verlag, pp. 235-242, 1972.Tait, P. G. "Remarks on the Colouring of Maps." Proc. Roy. Soc. Edingburg 10, 501-503, 1880.Walther, H. "Ein kubischer, planarer, zyklisch fünffach zusammenhängender Graf, der keinen Hamiltonkreis besizt." Wiss. Z. Hochschule Elektrotech. Ilmenau 11, 163-166, 1965.

请引用本文为

Weisstein, Eric W. “循环边连通性。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/CyclicEdgeConnectivity.html

学科分类