Minimum k-geodetically connected digraphs
A strong digraph is k-geodetically connected (k-GC) if the removal of at least k vertices is required to increase the distance between at least one pair of vertices or reduce it to a single vertex. Such digraphs can serve as models of distance invulnerable networks (immune to k -1 or fewer vertex failures) for a system with one-way communications. For every integer n, we determine the minimum size 2-GC digraphs of order n. Further, we find the minimum size of a k-GC digraph of order n if n equivalent to 0 (mod k) and give good bounds for all n. Also, several operations on and constructions of k-GC digraphs are presented. We show that the problem of finding a minimum size k-GC spanning subdigraph of a given digraph is NP-hard. (C) 2004 Wiley Periodicals, Inc.
distance invulnerability minimum-size digraph geodetic connectivity survivable network network design np-hard