Sufficient conditions for graphs to be λ′‐optimal and super‐λ′
Sufficient conditions for graphs to be λ′‐optimal and super‐λ′
复制标题
DOI：
10.1002/net.20173
复制
发表时间：
2007-05
期刊：
影响因子：
2.1
通讯作者：
Li Shang;Heping Zhang
中科院分区：
文献类型：
--
作者：
Li Shang;Heping Zhang
一个连通图G的边割S称为限制边割，如果G-S不包含孤立点。所有限制边割的最小基数称为G的限制边连通度λ′（G）。一个图G称为λ′-最优图，如果λ′（G）= λ ′（G），其中λ ′（G）是G的最小边度。一个图被称为超λ′，如果每个最小限制边割隔离一条边。本文首先改进和推广了Hellwig和Reynmann给出的任意图、二部图和直径为2的图的λ′-最优性的充分条件，并用例子说明了我们的结果是最佳的.第二，我们提供了一个简单的证明，其限制条件比Hellwig和Reinmann定理中的限制条件更少，该定理给出了二分图中λ′-最优性的充分条件。最后，我们分别给出了任意图、二部图和无三角形图以及直径为2的图是超λ′的充分条件，并证明了这些条件是最好的。© 2007 Wiley Periodicals，Inc. NETWORKS，Vol. 49（3），234-242 2007
An edge‐cut S of a connected graph G is called a restricted edge‐cut if G‐S contains no isolated vertices. The minimum cardinality of all restricted edge‐cuts is called the restricted edge‐connectivity λ′(G) of G. A graph G is said to be λ′‐optimal if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree of G. A graph is said to be super‐λ′ if every minimum restricted edge‐cut isolates an edge. In this paper, first, we improve and generalize the sufficient conditions for λ′‐optimality in arbitrary graphs, bipartite graphs, and graphs with diameter 2, which were given by Hellwig and Volkmann, and show using examples that our results are best possible. Second, we provide a simple proof with less restrictive conditions than in Hellwig and Volkmann's theorem that gives sufficient conditions for λ′‐optimality in bipartite graphs. We conclude by presenting sufficient conditions for arbitrary, bipartite, and triangle‐free graphs, and for graphs with diameter 2, to be super‐λ′ respectively, and demonstrate that these conditions are best possible. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 234–242 2007