Towards minimum k ‐geodetically connected graphs

A connected graph G 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 G to a single vertex. Such graphs can serve as models of distance invulnerable networks (immune to k − 1 or fewer vertex failures). We focus on the k ‐GC graphs which have the least possible number of edges for a given number of vertices. We survey known results and add several new ones. A lower bound on the size of a k ‐GC graph is presented which generalizes a known bound of Farley and Proskurowski and a conjecture on the minimum size is raised. Operations on and constructions of k ‐GC graphs related to the conjecture are given. We give two techniques that for certain orders produce the least size k ‐GC graphs known so far. © 2002 Wiley Periodicals, Inc.