𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The size of strength-maximal graphs

✍ Scribed by Hong-Jian Lai

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
381 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a graph and let k′(G) be the edge‐connectivity of G. The strength of G, denoted by k̄′(G), is the maximum value of k′(H), where H runs over all subgraphs of G. A simple graph G is called k‐maximal if k̄′(G) ≤ k but for any edge e ∈ E(G^c^), k̄′(G + e) ≥ k + 1. Let G be a k‐maximal graph of order n. In [3], Mader proved |E(G)| ≤ (n ‐ k)k + (). In this note, we shall show (n ‐ 1)k ‐ () In⌊n/k + 2)⌋ ≤ |E(G|, and characterize the extremal graphs. We shall also give a characterization of all k‐maximal graphs.

📜 SIMILAR VOLUMES

The Maximal Exceptional Graphs
The Maximal Exceptional Graphs
✍ D. Cvetković; M. Lepović; P. Rowlinson; S.K. Simić 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 170 KB
Independent sets of maximal size in tens
Independent sets of maximal size in tensor powers of vertex-transitive graphs
✍ Cheng Yeaw Ku; Benjamin B. McMillan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 2 views

## Abstract Let __G__ be a connected, nonbipartite vertex‐transitive graph. We prove that if the only independent sets of maximal cardinality in the tensor product __G__ × __G__ are the preimages of the independent sets of maximal cardinality in __G__ under projections, then the same holds for all

Centers of maximal outerplanar graphs
Centers of maximal outerplanar graphs
✍ Andrzej Proskurowski 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 178 KB

## Abstract The center of a graph is defined to be the subgraph induced by the set of vertices that have minimum eccentricities (i.e., minimum distance to the most distant vertices). It is shown that only seven graphs can be centers of maximal outerplanar graphs.

The Geometry of Convex Affine Maximal Gr
The Geometry of Convex Affine Maximal Graphs
✍ Jose Antonio Gálvez; Antonio Martínez; Francisco Milán 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 2 views
Irregularity strength of dense graphs
Irregularity strength of dense graphs
✍ Bill Cuckler; Felix Lazebnik 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract Let __G__ be a simple graph of order __n__ with no isolated vertices and no isolated edges. For a positive integer __w__, an assignment __f__ on __G__ is a function __f__: __E__(__G__) → {1, 2,…, __w__}. For a vertex __v__, __f__(__v__) is defined as the sum __f__(__e__) over all edges