✦ LIBER ✦

On Minimally (n, λ)-Connected Graphs

✍ Scribed by Atsushi Kaneko; Katsuhiro Ota

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 128 KB
Volume: 80
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.1979

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is (n, *)-connected if it satisfies the following conditions: (1) |V(G)| n+1; (2) for any subset S V(G) and any subset L E(G) with * |S| +|L| <n*, G&S&L is connected. The (n, *)-connectivity is a common extension of both the vertex-connectivity and the edge-connectivity. An (n, 1)-connected graph is an n-(vertex)-connected graph, and a (1, *)-connected graph is a *-edge-connected graph. An (n, *)-connected graph G is said to be minimally (n, *)-connected if for any edge e in E(G), G&e is not (n, *)-connected. Let G be a minimally (n, *)-connected graph and let W be the set of its vertices of degree more than n*. Then we first prove that for any subset W$ of W, the minimum degree of the subgraph of G induced by the vertex set W$ is less than or equal to *. This result is an extension of a theorem of Mader, which states that the subgraph of a minimally n-connected graph induced by the vertices of degree more than n is a forest. By using our result, we show that if G is a minimally (n, *)-connected graph, then ( 1

3n&1. Furthermore, we study the number of vertices of degree n* in a minimally n*-connected graph.

📜 SIMILAR VOLUMES

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.

On n-connected graphs

✍ Branko Grünbaum 📂 Article 📅 1969 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB

The main aim of the present note is the proof of a variant of the MENGER-WHITNEY theorem on n-connected graphs (Theorem 1 below). While the result itself is well known (being, for example, a special case of the theorem of MENGER mentioned in Remark I), two of its aspects deserve attention. First, it

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_

Minimal k-arc connected graphs

✍ D. R. Fulkerson; L. S. Shapley 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 364 KB

On Vertices of outdegree n in minimally

On Vertices of outdegree n in minimally n-connected digraphs

✍ W. Mader 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 1 views

## Abstract Let |__D__| and |D|^+^~__n__~ denote the number of vertices of __D__ and the number of vertices of outdegree __n__ in the digraph __D__, respectively. It is proved that every minimally __n__‐connected, finite digraph __D__ has |D|^+^~__n__~ ≥ __n__ + 1 and that for __n__ ≥ 2, there is a

The connectivity of minimal imperfect gr

The connectivity of minimal imperfect graphs

✍ Seb�, Andr�s 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 535 KB

We prove that partitionable graphs are 2w -2-connected, that this bound is sharp, and prove some structural properties of cutsets of cardinality 2w -2. The proof of the connectivity result is a simple linear algebraic proof.