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 rst 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 k62. 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).

Graphs with bounded induced distance

CICERONE, SERAFINO;DI STEFANO, GABRIELE
2001

Abstract

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 rst 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 k62. 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).
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/15198
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 4
social impact