半传递重图的限制性边连通度（英文）

田应智; 孟吉翔; 陈星

doi:10.13568/j.cnki.651094.2018.01.006

您当前的位置：

首页 >

文章列表页 >

半传递重图的限制性边连通度（英文）

更新时间：2026-01-21

- 半传递重图的限制性边连通度（英文）
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 35, Issue 1, Pages: 34-41(2018)
- 作者机构：
  
  1. 新疆大学数学与系统科学学院
  2. 新疆工程学院
- 作者简介：
- 基金信息：
- DOI：10.13568/j.cnki.651094.2018.01.006
  CLC： O157.5
- Published：2018
- 稿件说明：
移动端阅览
[1]田应智,孟吉翔,陈星.半传递重图的限制性边连通度（英文）[J],2018,35(01):34-41.
[1]田应智,孟吉翔,陈星.半传递重图的限制性边连通度（英文）[J],2018,35(01):34-41. DOI： 10.13568/j.cnki.651094.2018.01.006.

DOI：10.13568/j.cnki.651094.2018.01.006.

摘要

设G=(V

E)是一个重图(包含重边

但不含环).图G的边连通度

记为λ(G)

是G的最小边割的基数.我们称G是极大边连通的如果λ(G)=δ(G);称图G是超边连通的如果每个最小边割都是某个点的邻边集合.图G的限制性边连通度

记为λ(G)

是图G的最小限制性边割的基数.如果λ(G)达到限制性边连通度的上界

我们称G是λ-最优的.一个二部重图是半传递的如果它作用在每个部分上都是传递的.在本文中

我们将刻画极大边连通的、超边连通的、λ-最优的半传递重图.

Abstract

Let G =(V

E) be a multigraph(it has multiple edges

but no loops). The edge connectivity

denoted byλ(G)

is the cardinality of a minimum edge-cut of G. We call G maximally edge-connected if λ(G) = δ(G)

and G super edge-connected if every minimum edge-cut is a set of edges incident with some vertex. The restricted edge-connectivityλ(G) of G is the minimum number of edges whose removal disconnects G into non-trivial components. If λ(G) achieves the upper bound of restricted edge-connectivity

then G is said to be λ-optimal. A bipartite multigraph is said to be half-transitive if its automorphism group is transitive on the sets of its bipartition. In this paper

we will characterize maximally edge-connected half-transitive multigraphs

super edge-connected half-transitive multigraphs

and λ-optimal half-transitive multigraphs.

关键词

Keywords

references

Mader W.Minimale n-fach kantenzusammenh a¨ngenden Graphen[J].Mathematische Annalen,1971,191:21-28.

Liang X,Meng J.Connectivity of Connected Bipartite Graphs with Two Orbits[J].Lecture notes in computer science,Springer,Heidelberg,2007,4489:334-337.

Bauer D,Boesch F,Suffel C,et al.Combinatorial optimization problems in the analysis and design of probabilistic networks[J].Networks,1985,15:257-271.

Tindell R.Connectivity of Cayley digraphs[A].In Combinational Network Theory(D Z Du and D F Hsu eds).Kluwer Academic Publishers,1996,41-64.

Esfahanian A,Hakimi S.On computing a conditional edge-connectivity of a graph[J].Information Processing Letters,1988,27:195-199.

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

Esfahanian A.Generalized measures of fault tolerance with application to n-cube Networks[J].IEEE Transactions on Computers,1989,38(11):1586-1591.

Li Q,Li Q.Super edge connectivity of connected edge symmetric graphs[J].Networks,1999,33:157-159.

Lin H,Meng J,Yang W.Super restricted edge connectivity of regular graphs with two orbits[J].Applied Mathematics and Computation,2012,218:6656-6660.

Meng J,Ji Y.On a kind of restricted edge connectivity of graphs[J].Discrete Applied Mathematics,2002,117:183-193.

Tian Y,Meng J.On super restricted edge-connectivity of edge-transitive graphs[J].Discrete Mathematics,2010,310:2273-2279.

Wang Y.Super restricted edge-connectivity of vertex-transitive graphs[J].Discrete Mathematics,2004,289:199-205.

Yang W,Zhang Z,Qin C,et al.On super 2-restricted and 3-restricted edge-connected vertex transitive graphs[J].Discrete Mathematics,2011,311:2683-2689.

Yang W,Zhang Z,Guo X,et al.On the edge connectivity of graphs with two orbits of the same size[J].Discrete Mathematics,2011,311:1768-1777.

Zhang Z,Meng J.Restricted edge connectivity of edge transitive graphs[J].Ars Combinatoria,2006,78:297-308.

Zhang Z.Sufficient conditions for restricted-edge-connectivity to be optimal[J].Discrete Mathematics,2007 307:2891–2899.

张昭,黄晓辉.传递图中的限制性边连通性[J].新疆大学学报(自然科学版),2004,21(4):357-360.

Wang M,Li Q.Conditional edge connectivity properties,reliability comparison and transitivity of graphs[J].Discrete Mathematics,2002,258:205-214.

Li Q,Li Q.Reliability analysis of circulants[J].Networks,1998,31:61-65.

Meng J.Optimally super-edge-connected transitive graphs[J].Discrete Mathematics,2003,260:239-248.

Tian Y,Meng J,Liang X.On super restricted edge connectivity of half vertex transitive graphs[J].Graphs and Combinatorics,2012,28:287-296.

Tian Y,Meng J.On restricted edge-connectivity of vertex-transitive multigraphs[J].International Journal of Computer Mathematics,2014,91(8):1655-1661.

Tindell R.Connectivity of Cayley digraphs[J].Combinatorial Network Theory,Klumer,Dordrecht,1996,41-46.

Xu J,Xu K.On restricted edge connectivity of graphs[J].Discrete Mathematics,2002,243:291-298.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰