(k,+)-distance hereditary graphs (extended abstract)

In this work we introduce, characterize, and provide algorithmic results for (k, +)-distance-hereditary graphs. These graphs can be used to model interconnection networks with desirable connectivity properties; a network modeled as a (k, +)-distance-hereditary graph can be characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between these nodes in the faulty graph is bounded by k plus the distance in the non-faulty graph. The class of all these graphs is denoted by DH(k, +) By varying the parameter k, classes DH(k, +) form a hierarchy that represents a parametric extension of the well-known class of distance-hereditary graphs, and include all graphs.