Region Disjoint Paths in a Class of Optimal Line Graph Networks

Communication networks are one of the backbones to society, and it is important that they withstand failures. Improving the robustness of a network involves good algorithms for network connectivity and routing in the presence of faults. The importance of being able to connect the good parts of the network when catastrophic failures, natural or manmade, affect the system cannot be underestimated in either a military or a natural disaster situation. Traditional network robustness has been studied where point failures occur, with no reference to their locality. In reality, if regional failures are taken into consideration as the metric to evaluate the robustness of a network, then we can apply them to situations where simultaneous failures take place, but clustered in regions. Region Based Connectivity (RBC) was introduced in INFOCOM 2006, subsequent to which there have been some researchers who have looked at various aspects of this metric. In this paper, we look at the RBC of a class of uniform networks produced by recursive modified line graphs. This work deals with topological regions, and not geometric regions. The study shows that these networks display optimal RBC and calculates the upper bounds on the radius of these regions for optimal RBC.