Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
betweenness centrality; betweenness-uniform graph
betweenness centrality; betweenness-uniform graph
Summary:
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] Akiyama, J., Ando, K., Avis, D.: 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] Balakrishnan, K., Changat, M., Peterin, I., Špacapan, S., Šparl, P., Subhamathi, A. R.: 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] Buckley, F.: 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] Buckley, F.: 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] Caporossi, G., Paiva, M., Vukičević, D., Segatto, M.: 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] Comellas, F., Gago, S.: 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] Diestel, R.: Graph Theory. Graduate Texts in Mathematics 173, Springer, Berlin (2010). DOI 10.1007/978-3-662-53622-3 | MR 2744811 | Zbl 1204.05001
[8] Freeman, L. C.: A set of measures of centrality based on betweenness. Sociometry 40 (1977), 35-41. DOI 10.2307/3033543
[9] Gago, S., Hurajová, J. Coroničová, Madaras, T.: On betweenness-uniform graphs. Czech. Math. J. 63 (2013), 629-642. DOI 10.1007/s10587-013-0044-y | MR 3125646 | Zbl 1299.05085
[10] Knor, M., Madaras, T.: On farness- and reciprocally-selfcentric antisymmetric graphs. Congr. Numerantium 171 (2004), 173-178. MR 2122106 | Zbl 1064.05052
[11] Malnič, A., Marušič, D., Potočnik, P., Wang, C.: 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] Plesník, J.: 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] Weisstein, E. W.: Generalized Petersen Graph. From MathWorld---A Wolfram Web Resource available at http://mathworld.wolfram.com/GeneralizedPetersenGraph.html
Search
Partner of
