Sufficient conditions for λ′-optimality in graphs with girth g

✍ Scribed by C. Balbuena; P. García-Vázquez; X. Marcote

• Publisher: John Wiley and Sons
• Year: 2006
• Tongue: English
• Weight: 146 KB
• Volume: 52
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20150

✦ Synopsis

Abstract

For a connected graph the restricted edge‐connectivity λ′(G) is defined as the minimum cardinality of an edge‐cut over all edge‐cuts S such that there are no isolated vertices in G–S. A graph G is said to
be λ′‐optimal if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G defined as ξ(G) = min{d(u) + d(v) − 2:uv ∈ E(G)}, d(u) denoting the degree of a vertex u. A. Hellwig and L. Volkmann [Sufficient conditions for λ′‐optimality in graphs of diameter 2, Discrete Math 283 (2004), 113–120] gave a sufficient condition for λ′‐optimality in graphs of diameter 2. In this paper, we generalize this condition in graphs of diameter g − 1, g being the girth of the graph, and show that a graph G with diameter at most g − 2 is λ′‐optimal. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 73–86, 2006