Czechoslovak Mathematical Journal, Vol. 68, No. 2, pp. 293-306, 2018
More on betweenness-uniform graphs
Jana Coroničová Hurajová, Tomáš Madaras
Received February 26, 2016. Published online April 13, 2018.
Abstract: We study graphs whose vertices possess the same value of betweenness centrality (which is defined as the sum of relative numbers of shortest paths passing through a given vertex). Extending previously known results of S. Gago, J. Hurajová, T. Madaras (2013), we show that, apart of cycles, such graphs cannot contain 2-valent vertices and, moreover, are 3-connected if their diameter is 2. In addition, we prove that the betweenness uniformity is satisfied in a wide graph family of semi-symmetric graphs, which enables us to construct a variety of nontrivial cubic betweenness-uniform graphs.
References: [1] J. Akiyama, K. Ando, D. Avis: Miscellaneous properties of equi-eccentric graphs. Convexity and Graph Theory Proc. Conf., Jerusalem, 1981, Ann. Discrete Math. 20; North-Holland Mathematics Studies 87, North-Holland, Amsterdam (1984), 13-23. DOI 10.1016/S0304-0208(08)72802-0 | MR 0791008 | Zbl 0566.05053
[2] K. Balakrishnan, M. Changat, I. Peterin, S. Špacapan, P. Šparl, A. R. Subhamathi: Strongly distance-balanced graphs and graph products. Eur. J. Comb. 30 (2009), 1048-1053. DOI 10.1016/j.ejc.2008.09.018 | MR 2513907 | Zbl 1185.05052
[3] F. Buckley: Self-centered graphs with a given radius. Proc. 10th southeast. Conf. Combinatorics, Graph Theory and Computing, Boca Raton, 1979 Congr. Numerantium 23 (1979), 211-215. MR 0561047 | Zbl 0426.05034
[4] F. Buckley: Self-centered graphs. Proc. Conf., Jinan, 1986 Ann. N. Y. Acad. Sci. 576, New York Academy of Sciences, New York (1989), 71-78. DOI 10.1111/j.1749-6632.1989.tb16384.x | MR 1110802 | Zbl 0792.05050
[5] G. Caporossi, M. Paiva, D. Vukičević, M. Segatto: Centrality and betweenness: vertex and edge decomposition of the Wiener index. MATCH Commun. Math. Comput. Chem. 68 (2012), 293-302. MR 2986488 | Zbl 1289.05057
[6] F. Comellas, S. Gago: Spectral bounds for the betweenness of a graph. Linear Algebra Appl. 423 (2007), 74-80. DOI 10.1016/j.laa.2006.08.027 | MR 2312324 | Zbl 1114.05058
[7] R. Diestel: Graph Theory. Graduate Texts in Mathematics 173, Springer, Berlin (2010). DOI 10.1007/978-3-662-53622-3 | MR 2744811 | Zbl 1204.05001
[8] L. C. Freeman: A set of measures of centrality based on betweenness. Sociometry 40 (1977), 35-41. DOI 10.2307/3033543
[9] S. Gago, J. Coroničová Hurajová, T. Madaras: On betweenness-uniform graphs. Czech. Math. J. 63 (2013), 629-642. DOI 10.1007/s10587-013-0044-y | MR 3125646 | Zbl 1299.05085
[10] M. Knor, T. Madaras: On farness- and reciprocally-selfcentric antisymmetric graphs. Congr. Numerantium 171 (2004), 173-178. MR 2122106 | Zbl 1064.05052
[11] A. Malnič, D. Marušič, P. Potočnik, C. Wang: An infinite family of cubic edge- but not vertex-transitive graphs. Discrete Math. 280 (2004), 133-148. DOI 10.1016/j.disc.2003.07.004 | MR 2043804 | Zbl 1041.05039
[12] J. Plesník: On the sum of all distances in a graph or digraph. J. Graph Theory 8 (1984), 1-21. DOI 10.1002/jgt.3190080102 | MR 0732013 | Zbl 0552.05048
[13] E. W. Weisstein: Generalized Petersen Graph. From MathWorld - A Wolfram Web Resource, available at http://mathworld.wolfram.com/GeneralizedPetersenGraph.html.
Affiliations: Jana Coroničová Hurajová, Faculty of Business Economics with seat in Košice, University of Economics in Bratislava, Tajovského 13, 041 30 Košice, Slovak Republic, e-mail: jana.coronicova.hurajova@euke.sk; Tomáš Madaras, Institute of Mathematics, Faculty of Sciences, University of P. J. Šafárik, Jesenná 5, 040 01 Košice, Slovak Republic, e-mail: tomas.madaras@upjs.sk
