Distance connectivity in graphs and digraphs

✍ Scribed by Balbuena, M. C.; Carmona, A.; Fiol, M. A.

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 642 KB
• Volume: 22
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199608)22:4<281::aid-jgt1>3.0.co;2-h

✦ Synopsis

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 is defined similarly. The t-degree of G, h ( 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 K ( t ) = 6 ( t ) for all values of t. In this paper we give a construction of a digraph having D -1 positive arbitrary integers c2 5 . . . 5 c D , D > 3, as the values of its t-distance connectivities 4 2 ) = cz, . . . , K ( D ) = cD.

Besides, a digraph that shows the independence of the parameters ~( t ) , X ( t ) , and 6 ( 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.