The average scattering number of graphs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 3, pp. 263-272.

The scattering number of a graph is a measure of the vulnerability of a graph. In this paper we investigate a refinement that involves the average of a local version of the parameter. If v is a vertex in a connected graph G, then sc v (G)=max{ω(G-S v )-|S v |}, where the maximum is taken over all disconnecting sets S v of G that contain v. The average scattering number of G denoted by sc av (G), is defined as s c a v ( G ) = v V ( G ) s c v ( G ) n , where n will denote the number of vertices in graph G. Like the scattering number itself, this is a measure of the vulnerability of a graph, but it is more sensitive. Next, the relations between average scattering number and other parameters are determined. The average scattering number of some graph classes are obtained. Moreover, some results about the average scattering number of graphs obtained by graph operations are given.

DOI : 10.1051/ita/2016027
Classification : 05C40, 05C69, 68M10, 68R10
Mots clés : Connectivity, rupture degree, scattering number, average lower domination number, average lower independence number
Aslan, Ersin 1 ; Kilinç, Deniz 2 ; Yücalar, Fatih 3 ; Borandağ, Emin 4

1 Turgutlu Vocational Training School, Celal Bayar University, 45400 Manisa, Turkey.
2 Department of Software Engineering, Celal Bayar University, 45400 Manisa, Turkey.
3 Fatih Yücalar, Department of Software Engineering, Celal Bayar University, 45400 Manisa, Turkey.
4 Emin Borandağ, Department of Software Engineering, Celal Bayar University, 45400 Manisa, Turkey.
@article{ITA_2016__50_3_263_0,
     author = {Aslan, Ersin and Kilin\c{c}, Deniz and Y\"ucalar, Fatih and Boranda\u{g}, Emin},
     title = {The average scattering number of graphs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {263--272},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {3},
     year = {2016},
     doi = {10.1051/ita/2016027},
     mrnumber = {3582642},
     zbl = {1353.05073},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2016027/}
}
TY  - JOUR
AU  - Aslan, Ersin
AU  - Kilinç, Deniz
AU  - Yücalar, Fatih
AU  - Borandağ, Emin
TI  - The average scattering number of graphs
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 263
EP  - 272
VL  - 50
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2016027/
DO  - 10.1051/ita/2016027
LA  - en
ID  - ITA_2016__50_3_263_0
ER  - 
%0 Journal Article
%A Aslan, Ersin
%A Kilinç, Deniz
%A Yücalar, Fatih
%A Borandağ, Emin
%T The average scattering number of graphs
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 263-272
%V 50
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2016027/
%R 10.1051/ita/2016027
%G en
%F ITA_2016__50_3_263_0
Aslan, Ersin; Kilinç, Deniz; Yücalar, Fatih; Borandağ, Emin. The average scattering number of graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 3, pp. 263-272. doi : 10.1051/ita/2016027. http://archive.numdam.org/articles/10.1051/ita/2016027/

E. Aslan, The Average Lower Connectivity Of Graphs. J. Appl. Math. 2014 (2014) 1–4. | DOI | MR | Zbl

V. Chvatal, Tough Graphs and Hamiltonian Circuits. Discrete Math. 5 (1973) 215–228. | DOI | MR | Zbl

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

V. Giakoumakis, F. Roussel and H. Thuillier, Scattering Number and Modular Decomposition. Discrete Math. 165/166 (1997) 321–342. | DOI | MR | Zbl

F. Harary, Graph Theory. Addison-Wesley, New York (1994). | MR | Zbl

M.A. Henning and O.R. Oellermann, The Average Connectivity of a Digraph. Disc. Appl. Math. 140 (2004) 143–153. | DOI | MR | Zbl

H. A. Jung, On a Class of Posets and the Corresponding Comparability Graphs. J. Comb. Theory Ser. B 24 (1978) 125–133. | DOI | MR | Zbl

K. Ouyang and W. Yu, Relative Breaktivity of Graphs. J. Lanzhou Univ. Natural Sci. 29 (1993) 43–49. | Zbl

S. Zhang and S. Peng, Realitionships Between Scattering Number and Other Vulnerability Parameters. Int. J. Comput. Math. 81 (2004) 291–298. | DOI | MR | Zbl

S. Zhang and Z. Wang, Scattering Number in Graphs. Networks 37 (2001) 102–106. | DOI | MR | Zbl

Cité par Sources :