Graphs with bounded induced distance Original Research Article

In this work we introduce the class of graphs with bounded induced distance of order k, (BID(k) for short). A graph G belongs to BID(k) if the distance between any two nodes in every connected induced subgraph of G is at most k times their distance in G. These graphs can model communication networks in which node failures may occur: at a given time, if sender and receiver are still connected, any message can be delivered through a path (that, due to node failures, could be longer than the shortest one) the length of which is at most k times the best possible. In this work we first provide two characterizations of graphs belonging to BID(k): one based on the stretch number (a new invariant introduced here), and the other based on cycle-chord conditions. After that, we investigate classes with order k⩽2. In this context, we note that the class BID(1) is the well known class of distance-hereditary graphs, and we show that 3/2 is a lower bound for the order k of graphs that are not distance-hereditary. Then, we characterize graphs in BID(3/2) by means of forbidden induced subgraphs, and we also show that graphs in BID(2) have a more complex characterization. We prove that the recognition problem for the generic class BID(k) is Co-NP-complete. Finally, we show that the split composition can be used to generate graphs in BID(k).