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. Balbuena | 1 | 33 | 2.29 |
A. Carmona | 2 | 87 | 10.62 |
J. Fàbrega | 3 | 305 | 22.43 |
M. A. Fiol | 4 | 816 | 87.28 |