✦ LIBER ✦

The connectivity of large digraphs and graphs

✍ Scribed by M. A. Fiol

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 632 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170105

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order n, minimum degree δ, maximum degree Δ, diameter D, and a new parameter l~pi;~, 0 ≤ π ≤ δ − 2, related with the number of short paths (in the case of graphs l~0~ = ⌊(g − 1)/2⌋ where g stands for the girth). For instance, let G = (V,A) be a digraph on n vertices with maximum degree Δ and diameter D, so that n ≤ n(Δ, D) = 1 + Δ + Δ ^2^ + … + Δ^D^ (Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc‐connectivity of G,
equation image
.

📜 SIMILAR VOLUMES

Distance connectivity in graphs and digr

Distance connectivity in graphs and digraphs

✍ Balbuena, M. C.; Carmona, A.; Fiol, M. A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 642 KB

Let G = ( V , A ) be a digraph with diameter D # 1. For a given integer 2 5 t 5 D , the t-distance connectivity K ( t ) of G is the minimum cardinality of an z --+ y separating set over all the pairs of vertices z, y which are a t distance d(z, y) 2 t. The t-distance edge connectivity X ( t ) of G i

On the distance connectivity of graphs a

On the distance connectivity of graphs and digraphs

✍ M.A. Fiol; J. Fàbrega 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 475 KB

Let G=( V, E) be a digraph with diameter D # 1. For a given integer 1 t. The t-distance edge-connectivity of G is defined analogously. This paper studies some results on the distance connectivities of digraphs and bipartite digraphs. These results are given in terms of the parameter I, which can be

The superconnectivity of large digraphs

The superconnectivity of large digraphs and graphs

✍ M.A. Fiol 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 696 KB

On computing the connectivities of graph

On computing the connectivities of graphs and digraphs

✍ Abdol H. Esfahanian; S. Louis Hakimi 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 670 KB

Graphs and digraphs with given girth and

Graphs and digraphs with given girth and connectivity

✍ Jiping Liu; ; Huishan Zhou 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 230 KB

In this paper, we show that for any given two positive integers g and k with g > 3, there exists a graph (digraph) G with girth g and connectivity k. Applying this result, we give a negative answer to the problem proposed by M. Junger, G. Reinelt and W.R Pulleyblank (1985).

On the connectivity and the conditional

On the connectivity and the conditional diameter of graphs and digraphs

✍ Balbuena, C.; Carmona, A.; F�brega, J.; Fiol, M. A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 771 KB

Recently, it was proved that if the diameter D of a graph G is small enough in comparison with its girth, then G is maximally connected and that a similar result also holds for digraphs. More precisely, if the diameter D of a digraph G satisfies D 5 21 -1, then G has maximum connectivity ( K = 6 ) .