传递图中的限制性边连通度(英文)

Restricted Edge Connectivity in Transitive Graphs

设 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-

Let G=(V, E) be a connected graph and SE. 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.