✦ LIBER ✦

Graphs and digraphs with given girth and connectivity

✍ Scribed by Jiping Liu; ; Huishan Zhou

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 230 KB
Volume: 132
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)00576-d

No coin nor oath required. For personal study only.

✦ Synopsis

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).

📜 SIMILAR VOLUMES

Regular graphs with given girth pair

✍ Frank Harary; Peter Kovács 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 453 KB 👁 1 views

## Abstract The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair is proved and simple bounds for their smallest order are developed. Several infinite classes of such graphs are constructed and it is

Graphs with given connectivity propertie

Graphs with given connectivity properties

✍ Lawrencenko, Serge; Luo, Qiang 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB

A node of a graph G, thought of as representing a communication network, is said to be redundant provided that its removal does not diminish the connectivity. In constructing networks, we require reliable connectedness in addition to the usual requirement of reliability (i.e., the higher the connect

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

The connectivity of large digraphs and g

The connectivity of large digraphs and graphs

✍ M. A. Fiol 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 632 KB

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

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

Algorithms for constructing graphs and d

Algorithms for constructing graphs and digraphs with given valences and factors

✍ D.J. Kleitman; D.L. Wang 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 942 KB

Given a set of valences ( ui) such that { ui> and (vi-k} are both realizable as valences of graphs without loops or multiple edges, an explicit conslruction method is described for obtaining a graph with valences {ui] having a k-factor. A number of extensions of the result are obtained. Similar resu