Groupe d’études et de recherche en analyse des décisions

G-2017-31

Vertex and edge residual mean distances: New resilience measures for telecommunication networks

, , , , et

Any telecommunication network is subject to a node or link failure at any given time. Such a failure may impact the quality of the services provided by the network, and therefore the network resilience. In this paper, we define two new measures for evaluating network resilience with respect to a node or link failure: the vertex residual mean distance and the edge residual mean distance, in short RMDs. The RMDs are graph invariants which measure the impact of the removal of an arbitrary vertex/edge on the mean distance of the original graph. Some authors investigated different graph invariants before and after a vertex or an edge removal. However, to our knowledge, none of them incorporated graph invariant with vertex/edge removal. We study the RMDs on diverse graph classes, such as cycle graphs, complete graphs, twin graphs and \(k\)-geodetically connected graphs. We establish tight lower bound of the RMDs and graphs reaching them, as well as non-tight upper bound of the RMDs. Moreover, we conjecture tight upper bounds of the RMDs and graphs reaching them. From our results, we point out a family of graphs, i.e. twin graphs, that minimize the vertex residual mean distance and for which the edge residual mean distance is almost as small as that of the complete graph. Notice that each twin graph on \(n\) vertices has only \(2n-4\) edges, compared to the \(n(n-1)/2\) edges of the complete graph. Thus, twin graphs require relatively few edges to provide great levels of resilience. Since, in telecommunications, the number of edges is related to the cost of deploying the network, these results make it interesting to apply twin graphs for the physical topology design of telecommunication networks.

, 21 pages