On the centrality of some graphs

Abstract

  A central issue in the analysis of complex networks is the assessment of their stability and vulnerability. A variety of measures have been proposed in the literature to quantify the stability of networks and a number of graph-theoretic parameters have been used to derive formulas for calculating network reliability. Different measures for graph vulnerability have been introduced so far to study different aspects of the graph behavior after removal of vertices or links such as connectivity, toughness, scattering number, binding number, residual closeness and integrity. In this paper, we consider betweenness centrality of a graph. Betweenness centrality of a vertex of a graph is portion of the shortest paths all pairs of vertices passing through a given vertex. In this paper, we obtain exact values for betweenness centrality for some wheel related graphs namely gear, helm, sunflower and friendship graphs.

Keywords

• Network vulnerability,Network design and communication,Stability,Betweenness centrality of a graph,Gear graph,Helm graph

References

1. A. Brandstädt, V. B. Le, J. P. Spinrad: Graph classes: a survey, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999.
2. A. Aytaç, and Z. N. Odabaş: Residual Closeness of Wheels and Related Networks, Internat. J. Found. Comput. Sci., 22 , 1229-1240, 2011.
3. C. A. Barefoot, R. Entringer and H. Swart: Vulnerability in graphs–a comparative survey, J. Combin. Math. Combin. Comput., 1, 13 - 22, 1987.
4. D. R. Woodall: The binding number of a graph and its Anderson number, Journal of Combinatorial Theory, Series B, 15, 225 - 255, 1973.
5. F. Buckley and F. Harary: Distance in Graphs, Addison-Wesley Publishing Company Advanced Book Program, Redwood City, CA, 1990.
6. F. Comellas, S. Gago: Spectral bounds for the betweenness of a graph, Linear Algebra Appl., 423, 74 - 80, 2007.
7. G. Chartrand and L. Lesniak: Graphs and Digraphs, Second Edition, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986.
8. H. A. Jung: On a class of posets and the corresponding comparability graphs, Journal of Combinatorial Theory, Series B, 24 (2), 125 - 133, 1978.

9. H. Frank, I. T. Frisch: Analysis and design of survivable networks, IEEE Transactions on Communications Technology, 18(5), 501 - 519, 1970.
10. I. Javaid, S. Shokat: On the partition dimension of some wheel related graphs, Journal of Prime Research in Mathematics, 4, 154 - 164, 2008.
11. J. A. Gallian: A dynamic survey of graph labeling, Elect. Jour. Combin., 15, DS6, 2008.
12. M. Arockiaraj, P. Manuel, I. Rajasingh, B. Rajan: Wirelength of 1-fault hamiltonian graphs into wheels and fans Inform. Process. Lett., 111, 921-925, 2011.
13. L. C. Freeman: A set of measures of centrality based on betweenness, Sociometry, 40, No. 1, 35 - 41, 1977.
14. S. Gago, J. Hurajová and T. Madaras: Notes on the betweenness centrality of a graph, Math. Slovaca, 62, No. 1, 1-12, 2012.
15. T. Turaci and M. Ökten : Vulnerability Of Mycielski Graphs Via Residual Closeness, Ars Combinatoria, Volume CXVIII, 419 - 427, 2015.
16. V. Aytac and T. Turaci: Computing the closeness Centrality in Some Graphs, Submitted.
17. Z. N. Odabaş and A. Aytaç: Residual Closeness in Cycles and Related Networks, Fundamenta Informaticae, 124, 297 - 307, 2013.