Graphs with bounded induced distance (Q5928866)

The authors introduce the class BID(\(k\)) of graphs with bounded induced distance of order \(k\). A graph \(G\) belongs to BID(\(k\)) if the distance between any two vertices in every connected induced subgraph of \(G\) is at most \(k\) times their distance in \(G\). These graphs can model communication networks, and BID(1) corresponds to the class of distance-hereditary graphs. The authors give two characterizations of graphs belonging to BID(\(k\)). One is based on the so-called stretch number and the other on the cycle-chord condition. Furthermore, they investigate classes of order \(k\leq 2\) more precisely, and they show that the recognition problem for the class BID(\(k\)) is Co-NP-complete. Finally, the authors present some interesting open problems.