Computer or communication networks are so designed that they do not
easily get disrupted under external attack and, moreover, these are easily reconstructible
if they do get disrupted. These desirable properties of networks can be
measured by various graph parameters, such as connectivity, toughness, scattering
number, integrity, tenacity, rupture degree and edge-analogues of some of them.
Among these parameters, the tenacity and rupture degree are two better ones to
measure the stability of a network. In this paper, we consider two extremal problems
on the tenacity of graphs: determine the minimum and maximum tenacity of graphs
with given order and size. We give a complete solution to the first problem, while
for the second one, it turns out that the problem is much more complicated than that
of the minimum case. We determine the maximum tenacity of trees with given order and show the corresponding extremal graphs. The paper concludes with a discussion
of a related problem on the edge vulnerability parameters of graphs.
