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

张昭; 黄晓晖

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-01-21

- 传递图中的限制性边连通度(英文)
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Issue 4, (2004)
- 作者机构：
  
  新疆大学数学与系统科学学院,新疆大学后勤服务中心工程技术部新疆乌鲁木齐830046郑州大学数学系,河南郑州450052,新疆,乌鲁木齐,830046
- 作者简介：
- 基金信息：
- DOI：
  CLC： O157.5
- Published：2004
- 稿件说明：
移动端阅览
[1]张昭,黄晓晖.传递图中的限制性边连通度(英文)[J].新疆大学学报(自然科学版),2004(04):357-360.

张昭, 黄晓晖. 传递图中的限制性边连通度(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2004, (4).
[1]张昭,黄晓晖.传递图中的限制性边连通度(英文)[J].新疆大学学报(自然科学版),2004(04):357-360. DOI：

张昭, 黄晓晖. 传递图中的限制性边连通度(英文)[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

…

λ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 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.

关键词

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.

HararyF.Conditional connectivity[J].Networks,1983,13:347-357.

MengJX,JiY H.On a kind of restricted edge connectivity of graphs[J].DiscrMath,2002,117:183-193.

TindellR.Connectivity of cayley graphs[A].In:Combinatori alNetworkTheory(D.Z.Du andD.F.Hsueds.)1996,41-64.

WangM,LiQ.Conditional edge connectivity properties,reliability comparison and transitivity of graphs[J].DiscrMath,2002,258:205-214.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

超立方体外边连通度可靠性分析(英文)

对称群上Cayley图的连通性(英文)

Related Author

张明祖

孟吉翔

田应智

孟吉翔

Related Institution

新疆大学数学与系统科学学院

新疆大学数学物理研究所

⁰