𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On minimally k-edge-connected graphs and shortest k-edge-connected Steiner networks

✍ Scribed by Tibor Jordán

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
170 KB
Volume
131
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G = (V; E) is called minimally (k; T )-edge-connected with respect to some T ⊆ V if there exist k-edge-disjoint paths between every pair u; v ∈ T but this property fails by deleting any edge of G. We show that |V | can be bounded by a (linear) function of k and |T | if each vertex in V -T has odd degree. We prove similar bounds in the case when G is simple and k 6 3. These results are applied to prove structural properties of optimal solutions of the shortest k-edge-connected Steiner network problem. We also prove lower bounds on the corresponding Steiner ratio.

📜 SIMILAR VOLUMES

Minimally (k, k)-edge-connected graphs
Minimally (k, k)-edge-connected graphs
✍ Kamal Hennayake; Hong-Jian Lai; Deying Li; Jingzhong Mao 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB 👁 1 views

## 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_

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.

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