WSEAS Transactions on Mathematics
Print ISSN: 1109-2769, E-ISSN: 2224-2880
Volume 11, 2012
Some Results on Tenacity of Graphs
Author:
Abstract: The tenacity of an incomplete connected graph $$G$$ is defined as $$T(G)= {min \left \{ \frac{|S|+m(G−S)} {ω(G−S)}: S ⊂ V (G), ω(G − S) > 1
\right \} } $$ where $$ω(G − S) $$ and $$m(G − S) $$, respectively, denote the number of components and the order of a largest component in $$(G − S) $$ This is a reasonable parameter to measure the vulnerability of networks, as it takes into account both the amount of work done to damage the network and how badly the network is damaged. In this paper, we firstly give some results on the tenacity of gear graphs. After that, the tenacity of the lexicographic product of some special graphs are calculated. We also give the exact values for the tenacity of powers of paths. Finally, the relationships between the tenacity and some vulnerability parameters, namely the integrity, toughness and scattering number are established.