On Building Networks with Limited Stretch Factor

We consider non-reliable networks characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between any pair of such nodes in the faulty graph is at most k times the distance in the non- faulty graph. The smallest k that guarantees such property is called stretch factor of the network. In this work we review some known results about graphs that model networks with limited stretch factor and provide some new insights. In particular, we show that the split composition operation applied to minimal components like paths P3 and cycles C3 and C5 can be used to build networks with stretch factor less than two.