Flip-trees: fault-tolerant graphs with wide containers
F.J. Meyer · IEEE Transactions on Computers · 1988
A family of graphs is introduced with (d(d-1)/sup l/-2)/(d-2) nodes, where d is the degree of every node and l is any positive integer. The graphs have diameter 2l-1. In the presence of at most d-1 faults, the diameter increases to at most 2l+1. Furthermore, there exists a container (set of node-disjoint paths) of width d and length at most 2l+1 between every pair of nodes. The graphs are compared to those that have been proposed previously with respect to diameter, fault-tolerant diameter, container width, ease of routing, ease of fault-tolerant routing, and extensibility.>