𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Sufficient conditions for a graph to be super restricted edge-connected

✍ Scribed by Shiying Wang; Shangwei Lin

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
236 KB
Volume
51
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Restricted edge connectivity is a more refined network reliability index than edge connectivity. A restricted edge cut F of a connected graph G is an edge cut such that G‐F has no isolated vertex. The restricted edge connectivity λ′ is the minimum cardinality over all restricted edge cuts. We call G λ′‐optimal if λ′ = ξ, where ξ is the minimum edge degree in G. Moreover, a λ′‐optimal graph G is called a super restricted edge‐connected graph if every minimum restricted edge cut separates exactly one edge. Let D and g denote the diameter and girth of G, respectively. In this paper, we first present a necessary condition for non‐super restricted edge‐connected graphs with minimum degree δ ≥ 3 and D ≤ g − 2. Next, we prove that a connected graph with minimum degree δ ≥ 3 and D ≤ g − 3 is super restricted edge‐connected. Finally, we give some sufficient conditions on the conditional diameter and the girth for super restricted edge‐connected graphs. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

📜 SIMILAR VOLUMES

Neighborhood conditions for graphs to be
Neighborhood conditions for graphs to be super restricted edge connected
✍ Shiying Wang; Jing Li; Lihong Wu; Shangwei Lin 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 212 KB

## Abstract Restricted edge connectivity is a more refined network reliability index than edge connectivity. For a connected graph __G__ = (__V__, __E__), an edge set __S__ ⊆ __E__ is a restricted edge cut if __G__ − __S__ is disconnected and every component of __G__ − __S__ has at least two vertic

Sufficient conditions for graphs to be λ
Sufficient conditions for graphs to be λ′-optimal, super-edge-connected, and maximally edge-connected
✍ Angelika Hellwig; Lutz Volkmann 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB

## Abstract The restricted‐edge‐connectivity of a graph __G__, denoted by λ′(__G__), is defined as the minimum cardinality over all edge‐cuts __S__ of __G__, where __G__‐__S__ contains no isolated vertices. The graph __G__ is called λ′‐optimal, if λ′(__G__) = ξ(__G__), where ξ(__G__) is the minimum

A sufficient condition for bipartite gra
A sufficient condition for bipartite graphs to be type one
✍ Xu, Baogang 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 58 KB 👁 2 views

The total chromatic number χ T (G) of graph G is the least number of colors assigned to V (G) ∪ E(G) such that no adjacent or incident elements receive the same color. In this article, we give a sufficient condition for a bipartite graph G to have χ T (G) = ∆(G) + 1.

A sufficient condition for equality of e
A sufficient condition for equality of edge-connectivity and minimum degree of a graph
✍ Donald L. Goldsmith; Roger C. Entringer 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract Let __G__ be a connected graph of order __p__ ≥ 2, with edge‐connectivity κ~1~(__G__) and minimum degree δ(__G__). It is shown her ethat in order to obtain the equality κ~1~(__G__) = δ(__G__), it is sufficient that, for each vertex __x__ of minimum degree in __G__, the vertices in the n