𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Jerzy Topp; Lutz Volkmann

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
270 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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__ −3) if G is a p‐partite graph. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

A sufficient condition for equality of e
A sufficient condition for equality of edge-connectivity and minimum degree of a graph
✍ Donald L. Goldsmith; Roger C. Entringer 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

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

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

Realizability of p-point graphs with pre
Realizability of p-point graphs with prescribed minimum degree, maximum degree, and line connectivity
✍ F. T. Boesch; C. L. Suffel 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 316 KB

## Abstract It is well known that certain graph‐theoretic extremal questions play a central role in the study of communication network vulnerability. Herein we consider a generalization of some of the classical results in this area. We define a (__p__, Δ, δ, λ) graph as a graph having __p__ points,

The rainbow connection of a graph is (at
The rainbow connection of a graph is (at most) reciprocal to its minimum degree
✍ Michael Krivelevich; Raphael Yuster 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB 👁 1 views

## Abstract An edge‐colored graph __G__is __rainbow edge‐connected__ if any two vertices are connected by a path whose edges have distinct colors. The __rainbow connection__ of a connected graph __G__, denoted by __rc__(__G__), is the smallest number of colors that are needed in order to make __G__

A degree condition for the circumference
A degree condition for the circumference of a graph
✍ Nathaniel Dean; Pierre Fraisse 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 1 views

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let rn be any positive integer. Suppose G is a 2-connected graph with vertices x,, . . . , x, and edge set E that satisfies the proper