✦ LIBER ✦

Sufficient conditions for maximally connected dense graphs

✍ Scribed by Terunao Soneoka; Hiroshi Nakada; Makoto Imase; Claudine Peyrat

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 764 KB
Volume: 63
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(87)90151-8

No coin nor oath required. For personal study only.

✦ Synopsis

This paper considers the relations between the connectivity x or the edge-connectivity A of a graph and other parameters such as the number of vertices n, maximum degree A, minimum degree 6, diameter D and girth g. The following sufficient conditions for maximally connected graphs are derived.

6fir D <~g-2, g odd, [if D<~g 3, geven, .fif D<~g-1, godd, A = 0 [ ff D ~< g -2, g even.

These conditions are the best possible. From them some of the densest known graphs are proved to be maximally connected.

📜 SIMILAR VOLUMES

Sufficient conditions for graphs to be λ

Sufficient conditions for graphs to be λ′-optimal, super-edge-connected, and maximally edge-connected

✍ Angelika Hellwig; Lutz Volkmann 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB

## Abstract The restricted‐edge‐connectivity of a graph __G__, denoted by λ′(__G__), is defined as the minimum cardinality over all edge‐cuts __S__ of __G__, where __G__‐__S__ contains no isolated vertices. The graph __G__ is called λ′‐optimal, if λ′(__G__) = ξ(__G__), where ξ(__G__) is the minimum

Degree sequence conditions for maximally

Degree sequence conditions for maximally edge-connected graphs and digraphs

✍ Dankelmann, Peter; Volkmann, Lutz 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 88 KB 👁 2 views

In this paper we give simple degree sequence conditions for the equality of edge-connectivity and minimum degree of a (di-)graph. One of the conditions implies results by Bollobás, Goldsmith and White, and Xu. Moreover, we give analogue conditions for bipartite (di-)graphs.

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

Four sufficient conditions for hamiltoni

Four sufficient conditions for hamiltonian graphs

✍ A. Ainouche 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 290 KB

## Ainouche, A., Four sufficient conditions for hamiltonian graphs, Discrete Mathematics 89 (1991) 195-200.

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_

One sufficient condition for hamiltonian

One sufficient condition for hamiltonian graphs

✍ Guantao Chen 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 220 KB 👁 1 views

## Abstract Let __G__ be a 2‐connected graph of order __n.__ We show that if for each pair of nonadjacent vertices __x__,__y__ ∈ __V(G)__, then __G__ is Hamiltonian.