Issue |
RAIRO-Theor. Inf. Appl.
Volume 50, Number 3, July-September 2016
|
|
---|---|---|
Page(s) | 263 - 272 | |
DOI | https://doi.org/10.1051/ita/2016027 | |
Published online | 30 November 2016 |
The average scattering number of graphs
1 Turgutlu Vocational Training School,
Celal Bayar University, 45400
Manisa,
Turkey.
ersin.aslan@cbu.edu.tr
2 Department of Software Engineering,
Celal Bayar University, 45400
Manisa, Turkey.
deniz.kilinc@cbu.edu.tr
3 Fatih Yücalar, Department of Software
Engineering, Celal Bayar University, 45400
Manisa,
Turkey.
fatih.yucalar@cbu.edu.tr
4 Emin Borandağ, Department of Software
Engineering, Celal Bayar University, 45400
Manisa, Turkey.
emin.borandag@cbu.edu.tr
Received:
20
March
2016
Accepted:
22
November
2016
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 scv(G) = max { ω(G − Sv) − | Sv | }, where the maximum is taken over all disconnecting sets Sv of G that contain v. The average scattering number of G denoted by scav(G), is defined as scav(G) = Σv ∈ V(G) scv(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.
Mathematics Subject Classification: 05C40 / 05C69 / 68M10 / 68R10
Key words: Connectivity / rupture degree / scattering number / average lower domination number / average lower independence number
© EDP Sciences 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.