The average scattering number of graphs

Aslan, Ersin; Kilinç, Deniz; Yücalar, Fatih; Borandağ, Emin

doi:10.1051/ita/2016027

Aslan, Ersin ¹ ; Kilinç, Deniz ² ; Yücalar, Fatih ³ ; Borandağ, Emin ⁴

¹ Turgutlu Vocational Training School, Celal Bayar University, 45400 Manisa, Turkey.
² Department of Software Engineering, Celal Bayar University, 45400 Manisa, Turkey.
³ Fatih Yücalar, Department of Software Engineering, Celal Bayar University, 45400 Manisa, Turkey.
⁴ Emin Borandağ, Department of Software Engineering, Celal Bayar University, 45400 Manisa, Turkey.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 3, pp. 263-272.

Résumé

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 $s c_{v} (G) = m a x {ω (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 $s c_{a v} (G)$ , is defined as $s c_{a v} (G) = \frac{\sum_{v \in 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.

MR Zbl

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

Affiliations des auteurs :

Aslan, Ersin ¹ ; Kilinç, Deniz ² ; Yücalar, Fatih ³ ; Borandağ, Emin ⁴

@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/

Bibliographie
Cité par

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 :