张昭, 黄晓晖. 传递图中的限制性边连通度(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2004, (4).DOI：
传递图中的限制性边连通度(英文)
摘要
设 G =( V
E)是一个连通图
S E是一个边子集 .如果 G -S不再连通
且 G -S的每一个连通分支都至少含有 r个点
则称 S为一个 r-限制性边割 .最小 r-限制性边割中所含的边数为 G的 r-限制性边连通度
记作λr( G) .如果对所有的 i=1
…
r
λi( G)都达到其最大可能值
则称 G为λr- 最优图 .王铭和李乔证明了 :若 G是一个 d-正则的点传递图
d≥ 4
围长 g≥ 5
或者 G是一个 d-正则的边传递图
d≥ 4
围长 g≥ 4
则 G是λ(g - 1 ) -最优图 .本文推广了这一结果
证明了 :在同样的条件下
G是λg- 最优图
Abstract
Let G=(V
E) be a connected graph and SE. S is said to be a r-restricted edge cut
if G-S is disconnected and each component in G-S contains at least r vertices. λr(G) is the minimum size of all r-restricted edge cuts. A graph G is said to be λr-optimal
if λi(G) attains its maximum possible value for i=1
…
r. Wang M. and Li Q. have proved that a vertex-transitive graph with degree d≥4 and girth g≥5or a d-regular edge-transitive graph with d≥4 and g≥4 is λ_((g-1))-optimal. In this paper
we generalize this result by showing that these graphs are in fact λg-optimal.
关键词
Keywords
references
BauerD,BoeschF,SuffelC,VanSlykeR.On the validity of a reduction of reliable network design to a graph ex-tremal probel[J].IEEE Tran.Circuits andSystems,1989,34:1579-1581.
BondyJA,MurtyU S R.Graph theory and its application[M].AcademicPress,NorthHollandLondon:TheMacmil-lonPressLtd,1976.
BonsmaP,UeffingN,VolkmannL .Edge-cuts leaving components of order atleast three[J].DiscrMath2002,256:431-439.
EsfahanianA,HakimiS.On computing a conditional edgeconnectivity of a graph[J].Inform.Process.Lett1988,27:195-199.
FàbregaJ,FoilM A.On the extraconnectivity of graphs[J].DiscrMath,1996,155:49-57.
京公网安备11010802024621