Title
On the order and size of s-geodetic digraphs with given connectivity
Abstract
A digraph G = ( V , E ) with diameter D is said to be s-geodetic, for 1 ⩽ s ⩽ D , if between any pair of (not necessarily different) vertices x , y ϵ V there is at most one x → y path of length ⩽ s . Thus, any loopless digraph is at least 1-geodetic. A similar definition applies for a graph G , but in this case the concept is closely related to its girth g , for then G is s -geodetic with s = ⌊( g − 1)/2⌋. The case s = D corresponds to the so-called (strongly) geodetic (di)graphs. Some recent results have shown that if the order n of a (di)graph is big enough, then its vertex connectivity attains its maximum value. In other words, the (di)graph is maximally connected. Moreover, a similar result involving the size m (number of edges) and edge-connectivity applies. In this work we mainly show that the same conclusions can be reached if the order or size of a s -geodetic (di)graph is small enough. As a corollary, we find some Chartrand-type conditions to assure maximum connectivities. For example, when s ⩾ 2, a s -geodetic digraph is maximally connected if δ ⩾ ⌈ 5 n/2−1 ⌉ . Under similar hypotheses it is also shown that stronger measures of connectivity, such as the so-called super-connectivity, attain also their maximum possible values.
Year
DOI
Venue
1997
10.1016/S0012-365X(96)00314-7
Discrete Mathematics
Keywords
Field
DocType
s-geodetic digraph
Discrete mathematics,Graph,Geodetic datum,Combinatorics,Vertex (geometry),Vertex connectivity,Corollary,Digraph,Mathematics
Journal
Volume
Issue
ISSN
174
1
Discrete Mathematics
Citations 
PageRank 
References 
19
1.03
9
Authors
4
Name
Order
Citations
PageRank
M. C. Balbuena1332.29
A. Carmona28710.62
J. Fàbrega330522.43
M. A. Fiol481687.28