𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimally (k, k)-edge-connected graphs

✍ Scribed by Kamal Hennayake; Hong-Jian Lai; Deying Li; Jingzhong Mao

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
138 KB
Volume
44
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For an integer l > 1, the l‐edge‐connectivity of a connected graph with at least l vertices is the smallest number of edges whose removal results in a graph with l components. A connected graph G is (k, l)‐edge‐connected if the l‐edge‐connectivity of G is at least k. In this paper, we present a structural characterization of minimally (k, k)‐edge‐connected graphs. As a result, former characterizations of minimally (2, 2)‐edge‐connected graphs in [J of Graph Theory 3 (1979), 15–22] are extended. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 116–131, 2003

📜 SIMILAR VOLUMES

Minimally 2-edge connected graphs
Minimally 2-edge connected graphs
✍ G. Chaty; M. Chein 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 338 KB

## Abstract A constructive characterization of minimally 2‐edge connected graphs, similar to those of Dirac for minimally 2‐connected graphs is given.

Minimal k-arc connected graphs
Minimal k-arc connected graphs
✍ D. R. Fulkerson; L. S. Shapley 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 364 KB
k-shredders in k-connected graphs
k-shredders in k-connected graphs
✍ Yoshimi Egawa 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract For a graph __G__, a subset __S__ of __V__(__G__) is called a shredder if __G__ − __S__ consists of three or more components. We show that if __k__ ≥ 4 and __G__ is a __k__‐connected graph, then the number of shredders of cardinality __k__ of __G__ is less than 2|__V__(__G__)|/3 (we sho

The number of vertices of degree k in a
The number of vertices of degree k in a minimally k-edge-connected digraph
✍ Yuan Xu-dong; Kang Liying; Cai Mao-cheng 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB 👁 2 views

Let k be a positive integer, and D = (V (D), E(D)) be a minimally k-edge-connected simple digraph. We denote the outdegree and indegree of x ∈ V (D) by δ D (x) and ρ D (x), respectively. Let u + (D) denote the number of vertices W. Mader asked the following question in [Mader, in Paul Erdös is Eigh

Contractible Edges and Triangles in k-Co
Contractible Edges and Triangles in k-Connected Graphs
✍ Ken-ichi Kawarabayashi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 129 KB

It is proved that if G is a k-connected graph which does not contain K - 4 , then G has an edge e or a triangle T such that the graph obtained from G by connecting e or by contracting T is still k-connected. By using this theorem, we prove some theorems which are generalizations of earlier work. In