𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximally connected digraphs

✍ Scribed by J. Fàbrega; M. A. Fiol

Publisher
John Wiley and Sons
Year
1989
Tongue
English
Weight
581 KB
Volume
13
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

This paper introduces a new parameter / = / ( G ) for a loopless digraph G, which can be thought of as a generalization of the girth of a graph. Let K, A, 6, and D denote respectively the connectivity, arc-connectivity, minimum degree, and diameter of G. Then it is proved that A = 6 if D s 21 and K = 6 if D I 21 -1. Analogous results involving upper bounds for K and A are given for the more general class of digraphs with loops. Sufficient conditions for a digraph to be super-A and super-rc are also given. As a corollary, maximally connected and superconnected iterated line digraphs and (undirected) graphs are characterized.

📜 SIMILAR VOLUMES

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.

On super-edge-connected digraphs and bip
On super-edge-connected digraphs and bipartite digraphs
✍ M. A. Fiol 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 524 KB

## Abstract A maximally edge‐connected digraph is called super‐λ if every minimum edge disconnecting set is trivial, i.e., it consists of the edges adjacent to or from a given vertex. In this paper sufficient conditions for a digraph to be super‐λ are presented in terms of parameters such as diamet

Sufficient conditions for maximally conn
Sufficient conditions for maximally connected dense graphs
✍ Terunao Soneoka; Hiroshi Nakada; Makoto Imase; Claudine Peyrat 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 764 KB

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

Connectivity of circulant digraphs
Connectivity of circulant digraphs
✍ Erik A. Van Doorn 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

An explicit expression is derived for the connectivity of circulant digraphs.