Abstract | ||
---|---|---|
Let G = (V, A) be a digraph with diameter D not equal 1. For a given integer 2 less than or equal to t less than or equal to D, the t-distance connectivity kappa(t) of G is the minimum cardinality of an x --> y separating set over all the pairs of vertices x, y which are at distance d(x, y) greater than or equal to t. The t-distnnce edge connectivity lambda(t) of G is defined similarly. The t-degree of G, delta(t), is the minimum among the out-degrees and in-degrees of all vertices with (out- or in-) eccentricity at least t. A digraph is said to be maximally distance connected if kappa(t) = delta(t) for all values of t. In this paper we give a construction of a digraph having D - 1 positive arbitrary integers c(2) less than or equal to ... less than or equal to c(D), D > 3, as the values of its t-distance connectivities kappa(2) = c(2),...,kappa(D) = c(D). Besides, a digraph that shows the independence of the parameters kappa(t), lambda(t), and delta(t) is constructed. Also we derive some results on the distance connectivities of digraphs, as well as sufficient conditions for a digraph to be maximally distance connected. Similar results for (undirected) graphs are presented. (C) 1996 John Wiley & Sons, Inc. |
Year | DOI | Venue |
---|---|---|
1996 | 3.0.CO;2-H" target="_self" class="small-link-text"10.1002/(SICI)1097-0118(199608)22:43.0.CO;2-H | Journal of Graph Theory |
DocType | Volume | Issue |
Journal | 22 | 4 |
ISSN | Citations | PageRank |
0364-9024 | 8 | 0.63 |
References | Authors | |
4 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
M. C. Balbuena | 1 | 33 | 2.29 |
A. Carmona | 2 | 87 | 10.62 |
M. A. Fiol | 3 | 816 | 87.28 |