An Interesting Structural Property Related to the Problem of Computing All the Best Swap Edges of a Tree Spanner in Unweighted Graphs

07/09/2018

∙

by   Davide Bilò, et al.

∙

0

∙

share

In this draft we prove an interesting structural property related to the problem of computing all the best swap edges of a tree spanner in unweighted graphs. Previous papers show that the maximum stretch factor of the tree where a failing edge is temporarily swapped with any other available edge that reconnects the tree depends only on the critical edge. However, in principle, each of the O(n^2) swap edges, where n is the number of vertices of the tree, may have its own critical edge. In this draft we show that there are at most 6 critical edges, i.e., each tree edge e has a critical set of size at most 6 such that, a critical edge of each swap edge of e is contained in the critical set.