✦ LIBER ✦

A sufficient condition for equality of edge-connectivity and minimum degree of a graph

✍ Scribed by Donald L. Goldsmith; Roger C. Entringer

Publisher: John Wiley and Sons
Year: 1979
Tongue: English
Weight: 184 KB
Volume: 3
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190030307

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a connected graph of order p ≥ 2, with edge‐connectivity κ~1~(G) and minimum degree δ(G). It is shown her ethat in order to obtain the equality κ~1~(G) = δ(G), it is sufficient that, for each vertex x of minimum degree in G, the vertices in the neighbourhood N(x) of x have sufficiently large degree sum. This result implies a previous result of Chartrand, which required that δ(G) ≥ [p/2].

📜 SIMILAR VOLUMES

Sufficient conditions for equality of co

Sufficient conditions for equality of connectivity and minimum degree of a graph

✍ Jerzy Topp; Lutz Volkmann 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 270 KB 👁 1 views

## Abstract For a graph __G__, let __n__(__G__), κ(__G__) and δ(__G__) denote the order, the connectivity, and the minimum degree of __G__, respectively. The paper contains some conditions on __G__ implying κ(__G__) = δ(__G__). One of the conditions is that __n__(__G__) ≤ δ(__G__)(2__p__ −1)/(2__p_

Sufficient degree conditions for k-edge-

Sufficient degree conditions for k-edge-connectedness of a graph

✍ D. Bauer; S.L. Hakimi; N. Kahl; E. Schmeichel 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB

Degree sequence conditions for equal edg

Degree sequence conditions for equal edge-connectivity and minimum degree, depending on the clique number

✍ Lutz Volkmann 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 87 KB

## Abstract Using the well‐known Theorem of Turán, we present in this paper degree sequence conditions for the equality of edge‐connectivity and minimum degree, depending on the clique number of a graph. Different examples will show that these conditions are best possible and independent of all the

Sufficient conditions for a graph to be

Sufficient conditions for a graph to be super restricted edge-connected

✍ Shiying Wang; Shangwei Lin 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB

## Abstract Restricted edge connectivity is a more refined network reliability index than edge connectivity. A restricted edge cut __F__ of a connected graph __G__ is an edge cut such that __G__‐__F__ has no isolated vertex. The restricted edge connectivity λ′ is the minimum cardinality over all re

A Degree Sum Condition for the Existence

A Degree Sum Condition for the Existence of a Contractible Edge in a κ-Connected Graph

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 184 KB

It is known that a noncomplete }-connected graph of minimum degree of at least w 5} 4 x contains a }-contractible edge, i.e., an edge whose contraction yields again a }-connected graph. Here we prove the stronger statement that a noncomplete }-connected graph for which the sum of the degrees of any

Minimum augmentation of a tree to a K-ed

Minimum augmentation of a tree to a K-edge-connected graph

✍ Shuichi Ueno; Yoji Kajitani; Hajime Wada 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB