Extreme tenacity of graphs with given order and size

Details Extreme tenacity of graphs with given order and size Extreme tenacity of graphs with given order and size

2011-09-21

arxiv.org/abs/1109.4673v1

Mathematics

Combinatorics

Scientific paper

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 and unicyclic graphs with given order and show the corresponding extremal graphs. These results are helpful in constructing stable networks with lower costs. The paper concludes with a discussion of a related problem on the edge vulnerability parameters of graphs.

Affiliated with

Also associated with

No associations

Rating

Extreme tenacity of graphs with given order and size does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extreme tenacity of graphs with given order and size, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extreme tenacity of graphs with given order and size will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-261812