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

Restricted Connectivity of the Line Graph of Hypercube

作　　者：林辉球[1] 孟吉翔[1] 田应智[1] 

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830046

出　　处：《新疆大学学报（自然科学版）》2010年第1期23-26,共4页Journal of Xinjiang University(Natural Science Edition)

基　　金：The research is supported by NSFC(No.10671165)

摘　　要：子集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.

关 键 词：线图 立方体 限制性点连通度 限制性边连通度 

分 类 号：O157.5[理学—数学]