Premium
Towards minimum k ‐geodetically connected graphs
Author(s) -
Plesník Ján
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10060
Subject(s) - combinatorics , conjecture , vertex (graph theory) , mathematics , upper and lower bounds , clique sum , metric dimension , vertex connectivity , graph , discrete mathematics , chordal graph , 1 planar graph , mathematical analysis
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.