新疆大学学报(自然科学版)
新疆大學學報(自然科學版)
신강대학학보(자연과학판)
XINJIANG UNIVERSITY JOURNAL(NATURAL SCIENCE EDITION)
2010年
1期
23-26
,共4页
线图%立方体%限制性点连通度%限制性边连通度
線圖%立方體%限製性點連通度%限製性邊連通度
선도%립방체%한제성점련통도%한제성변련통도
line graph%hypercube%restricted-edge-cut%restricted-edge-connectivity
子集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)是立方体的线图.
子集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)是立方體的線圖.
자집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 C 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 (∈) V(G) is called a Rg-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 Rg-vertex-cut is called the Rg-vertex connectivity of G, denoted by κg(G). In this paper, we prove that κ1(L(Qn)) = 3n-4,κ2 (L(Qn)) = 4n - 8, where L(Qn) is the line graph of Qn.