Relationships between vertex attack tolerance and other vulnerability parameters
Aytaç, Vecdi1 ; Turaci, Tufan2
1 Computer Engineering Department Faculty of Engineering, Ege University, 35100, Bornova-IZMIR, Turkey
2 Department of Mathematics, Faculty of Science, Karabük University, 78050, Karabük, Turkey
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 1, pp. 17-27.

Let G(V,E) be a simple undirected graph. Recently, the vertex attack tolerance (VAT) of G has been defined as τ(G) = min {|S| / |V-S-Cmax (G-S)|+1 : S ⊂ V} , where C max (G-S) is the order of a largest connected component in G-S. This parameter has been used to measure the vulnerability of networks. The vertex attack tolerance is the only measure that fully captures both the major bottlenecks of a network and the resulting component size distribution upon targeted node attacks. In this article, the relationships between the vertex attack tolerance and some other vulnerability parameters, namely connectivity, toughness, integrity, scattering number, tenacity, binding number and rupture degree have been determined.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2017005
Classification : 05C40, 68M10, 68R10
Mots-clés : Graph vulnerability, vertex attack tolerance, connectivity, network design and communication, toughness, integrity, scattering number, tenacity, binding number, rupture degree
Aytaç, Vecdi 1 ; Turaci, Tufan 2

1 Computer Engineering Department Faculty of Engineering, Ege University, 35100, Bornova-IZMIR, Turkey
2 Department of Mathematics, Faculty of Science, Karabük University, 78050, Karabük, Turkey 
@article{ITA_2017__51_1_17_0,
     author = {Ayta\c{c}, Vecdi and Turaci, Tufan},
     title = {Relationships between vertex attack tolerance and other vulnerability parameters},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {17--27},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {1},
     year = {2017},
     doi = {10.1051/ita/2017005},
     mrnumber = {3678027},
     zbl = {1369.05124},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2017005/}
}
TY  - JOUR
AU  - Aytaç, Vecdi
AU  - Turaci, Tufan
TI  - Relationships between vertex attack tolerance and other vulnerability parameters
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2017
SP  - 17
EP  - 27
VL  - 51
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2017005/
DO  - 10.1051/ita/2017005
LA  - en
ID  - ITA_2017__51_1_17_0
ER  - 
%0 Journal Article
%A Aytaç, Vecdi
%A Turaci, Tufan
%T Relationships between vertex attack tolerance and other vulnerability parameters
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2017
%P 17-27
%V 51
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2017005/
%R 10.1051/ita/2017005
%G en
%F ITA_2017__51_1_17_0
Aytaç, Vecdi; Turaci, Tufan. Relationships between vertex attack tolerance and other vulnerability parameters. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 1, pp. 17-27. doi : 10.1051/ita/2017005. http://archive.numdam.org/articles/10.1051/ita/2017005/

C.A. Barefoot, R. Entringer and H. Swart, Vulnerability in graphs a comparative survey. J. Comb. Math. Comb. Comput. 1 (1987) 12–22. | MR | Zbl

M. Cozzens, D. Moazzami and S. Stueckle, The tenacity of a graph. Proc. 7th International Conference on the Theory and Applications of Graphs. Wiley, New York (1995) 1111–1122. | MR | Zbl

V. Chvátal, Tough graphs and Hamiltonian circuits. Discrete Math. 5 (1973) 215–228. | DOI | MR | Zbl

G. Ercal, On Vertex Attack Tolerance in Regular Graphs. Preprint [cs.DM] (2014). | arXiv

G. Ercal and J. Matta. Resilience notions for scale-free networks. Procedia Comput. Sci. 20 (2013) 510–515. | DOI

D.B. West, Introduction to Graph Theory. Prentice Hall, NJ (2001). | MR

D.R. Woodall, The binding number of a graph and its Anderson number. J. Combin. Theory Ser. B 15 (1973) 225–255. | DOI | MR | Zbl

H. Frank and I.T. Frisch, Analysis and design of survivable Networks. IEEE Trans. Commun. Technol. 18 (1970) 501–519. | DOI | MR

H.A. Jung. On maximal circuits infinite graphs. Ann. Discrete Math. 3 (1978) 129–144. | DOI | MR | Zbl

I. Mishkovski, M. Biey and L. Kocarev, Vulnerability of complex Networks. Commun. Nonl. Sci. Numer. Simul. 16 (2011) 341–349. | DOI | MR | Zbl

J. Matta, J. Borwey and G. Ercal, Comparative Resilience Notions and Vertex Attack Tolerance of Scale-Free Networks. Preprint [cs.SI] (2014). | arXiv

J. Matta, Comparing the Effectiveness of Resilience Measures. MSC Thesis, Southern Illinois University Edwardsville, USA (2014).

K.T. Newport and P.K. Varshney, Design of survivable communication networks under performance constraints. IEEE Trans. Reliab. 40 433-440 (1991). | DOI | Zbl

Y. Li, S. Zhang and X. Li, Rupture degree of graphs. Inter. J. Comput. Math. 82 (2005) 793–803. | DOI | MR | Zbl

Cité par Sources :