主題
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

使用 探索

參考文獻

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. “迴圈邊連通性。” 來自 Web 資源。 https://mathworld.tw/CyclicEdgeConnectivity.html

學科分類