Extreme Tenacity of Graphs with Given Order and Size
- PDF / 230,597 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 226 Views
Extreme Tenacity of Graphs with Given Order and Size T. C. E. Cheng • Yin-Kui Li • Chuan-Dong Xu Sheng-Gui Zhang
•
Received: 6 April 2014 / Revised: 25 July 2014 / Accepted: 28 July 2014 / Published online: 14 August 2014 Ó Operations Research Society of China, Periodicals Agency of Shanghai University, and SpringerVerlag Berlin Heidelberg 2014
Abstract 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 This work was supported by National Natural Science Foundation of China (No. 11271300), the Open Fund of Xi’an Jiaotong University, China (No. 2010-4) and the Fund of Qinghai University for Nationalities (xjz201403). T. C. E. Cheng Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China Y.-K. Li School of Mathematics and Statistics, Qinghai University for Nationalities, Xining 810000, Qinghai, China C.-D. Xu S.-G. Zhang Department of Applied Mathematics, Northwestern Polytechnical University, Xi’an 710072, Shaanxi, China S.-G. Zhang (&) State Key Laboratory for Manufacturing Systems Engineering, Xi’an Jiaotong University, Xi’an 710049, Shaanxi, China e-mail: [email protected]
123
308
T. C. E. Cheng et al.
and show the corresponding extremal graphs. The paper concludes with a discussion of a related problem on the edge vulnerability parameters of graphs. Keywords Trees
Vulnerability parameters Minimum tenacity Maximum tenacity
1 Introduction In the analysis of the vulnerability of networks to disruption, three quantities (there may be others) came to mind, i.e., (1) the number of elements that are not functioning; (2) the number of remaining connected subnetworks and (3) the size of a largest remaining group within which mutual communication can still occur. Based on these quantities, many graph parameters, such as connectivity, toughness [5], scattering number [14], integrity [1], tenacity [6], rupture degree [15] and edge-analogues of some of them, have been proposed for measuring the vulnerability of networks. Throughout the paper, we use Bondy and Murty [3] for terminology and notation not defined here. For a graph G, by xðGÞ we denote the number of components of G, and sðGÞ the order of a largest component of G.
Data Loading...
