Premium
Sufficient conditions for graphs to be λ′ ‐optimal and super‐ λ′
Author(s) -
Shang Li,
Zhang Heping
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20173
Subject(s) - combinatorics , bipartite graph , mathematics , enhanced data rates for gsm evolution , graph , cardinality (data modeling) , discrete mathematics , computer science , telecommunications , data mining
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