Towards minimum k‐geodetically connected graphs
Ján Plesnı́k · Networks · 2002
Abstract 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.