立方体的线图的限制性连通度(英文)

Restricted Connectivity of the Line Graph of Hypercube

子集SE(G)称为是图G的4-限制性边割,如果G-S不连通且每个连通分支至少有4个点.图G中基数最小的4-限制性边割称为4-限制性边连通度,记为λ4(G).本文确定了λ4(Qn)=4n-8.类似的,子集FV(G)称为图G的Rg-限制性点割,如果G-F不连通且每个连通分支的最小度不小于g.基数最小的Rg-限制性点割称为图G的Rg-限制性点连通度,记为κg(G).本文确定了κ1(L(Qn))=3n-4,κ2(L(Qn))=4n-8,其中L(Qn)是立方体的线图.

A subset S belong to E（G） is called a 4-restricted-edge-cut of G, if G - S is disconnected and every component contains at least 4 vertices. The minimum cardinality over all 4-restricted-edge-cut of G is called the 4-restricted-edge connectivity of G, denoted by λ4（G）. In this paper, we prove that λ4（Qn） = 4n - 8. Similarly, a subset F belong to V（G） is called a R^g-vertex cut of G, if G- F is disconnected and each vertex u ∈ V（G）- F has at least g neighbors in G- F. The minimum cardinality of all R^g-vertex-cut is called the R^g-vertex connectivity of G, denoted by k^g（G）. In this paper, we prove that k^1（L（Qn）） = 3n- 4, k^2（L（Qn））=4n-8, where L（Qn） is the line graph of Qn.