Tree robustness of a graph

Abstract

The spanning tree packing number of a graph G, denoted by STP(G), is the maximum number of edge-disjoint spanning trees contained in G. Let denotes the set of all spanning trees of G. We say that a spanning tree T of G is of type () if the maximum number of edge-disjoint spanning trees contained in (subgraph obtained by deleting all edges of T) is , in other words . The set of all ’s types of spanning trees gives a partition of . We introduce st-robustness of a graph as a new connectivity measure that evaluates the connectivity of a graph in case of deleting some of its spanning trees. st-robustness of a graph G, denoted by STR(G), is defined as the expected value of , when T ranges over all spanning trees of G. In this paper we study this parameter and evaluate it in the case of complete graphs.

Keywords:

• Spanning tree packing number
• robustness
• connectivity measure

AMS Subject Classifications:

• 05C05
• 05C35

View correction statement:

Erratum

Acknowledgements

The authors would like to thank the referee for his/her helpful comments on this manuscript.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The research of R. Tusserkani was supported by a grant from Institute for Research in Fundamental Sciences (IPM) [grant number 91920130].