Graphs with bounded induced distance

In this work we introduce "graphs with bounded induced distance" of order k (BID(k) for short). In any graph belonging to BID(k), the length of every induced path between every pair of nodes is at most k times the distance between the same nodes. In communication networks modeled by these graphs any message can be always delivered through a path whose length is at most k times the best possible one, even if some nodes fail. In this work we first provide a characterization of graphs in BID(k) by means of 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 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 their minimal 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).