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

Graphs with bounded induced distance

CICERONE, SERAFINO;DI STEFANO, GABRIELE
1998-01-01

Abstract

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).
1998
3-540-65195-0
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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: https://hdl.handle.net/11697/39851
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 1
social impact