The stress of a graph

Document Type : Original paper


1 Department of Data Science, PSPH, Manipal Academy of Higher Education, Manipal

2 Department of Mathematics, MIT, Manipal Academy of Higher Education, Manipal

3 Director (n-CARDMATH) Kalasalingam University Anand Nagar, Krishnankoil-626 126 Tamil Nadu, India

4 Centre for Advanced Research in Applied Mathematics and Statistics, Manipal Academy of Higher Education, Manipal


Stress is an important centrality measure of graphs applicable to the study of social and biological networks. We study the stress of paths, cycles, fans and wheels. We determine the stress of a cut vertex of a graph $G$, when $G$ has at most two cut vertices. We have also identified the graphs with minimum stress and maximum stress in the family of all trees of order $n$ and in the family of all complete bipartite graphs of order $n$.


Main Subjects

[1] S.P. Borgatti and M.G. Everett, A graph-theoretic perspective on centrality, Social Networks 28 (2006), no. 4, 466–484.
[2] G. Chartrand and L. Lesniak, Graphs & digraphs, Chapman and Hall, CRC, Boca Raton, 2005.
[3] R.C. Entringer, D.E. Jackson, and D.A. Snyder, Distance in graphs, Czechoslovak Math. J. 26 (1976), no. 2, 283–296.
[4] M Indhumathy, S Arumugam, V Baths, and T. Singh, Graph theoretic concepts in the study of biological networks, Applied Analysis in Biological and Physical Sciences (Cushing J., Saleem M., Srivastava H., Khan M., and Merajuddin M.,
eds.), Springer Proceedings in Mathematics & Statistics, vol 186. Springer, New Delhi, 2016, pp. 187–200.
[5] C. Kang, C. Molinaro, S. Kraus, Y. Shavitt, and V.S. Subramaniam, Diffusion centrality in social networks, IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Istanbul, 2012, pp. 558–564.
[6] D. Koschützki and F. Schreiber, Comparison of centralities for biological networks, German Conference on Bioinformatics, Gesellschaft für Informatik eV, 2004, pp. 161–174.
[7] R. Lopez, J. Worrell, H. Wickus, R. Flórez, and D.A. Narayan, Towards a characterization of graphs with distinct betweenness centralities., Australas. J. Comb. 68 (2017), no. 2, 285–303. 
[8] S.K. Raghavan Unnithan, B. Kannan, and M. Jathavedan, Betweenness centrality in some classes of graphs, Int. J. Comb. 2014 (2014), Article ID 241723.
[9] P. Shannon, A. Markiel, O. Ozier, N.S. Baliga, J.T. Wang, D. Ramage, N. Amin, B. Schwikowski, and T. Ideker, Cytoscape: A software environment for integrated models of biomolecular interaction networks, Genome Res. 13 (2003), no. 11,
[10] A. Shimbel, Structural parameters of communication networks, The Bulletin of Mathematical Biophysics 15 (1953), no. 4, 501–507.