| Title:
|
More on betweenness-uniform graphs (English) |
| Author:
|
Coroničová Hurajová, Jana |
| Author:
|
Madaras, Tomáš |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
68 |
| Issue:
|
2 |
| Year:
|
2018 |
| Pages:
|
293-306 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
betweenness centrality |
| Keyword:
|
betweenness-uniform graph |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 06890374 |
| idMR:
|
MR3819175 |
| DOI:
|
10.21136/CMJ.2018.0087-16 |
| . |
| Date available:
|
2018-06-11T10:50:22Z |
| Last updated:
|
2020-07-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147219 |
| . |
| Reference:
|
[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. Zbl 0566.05053, MR 0791008, 10.1016/S0304-0208(08)72802-0 |
| Reference:
|
[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. Zbl 1185.05052, MR 2513907, 10.1016/j.ejc.2008.09.018 |
| Reference:
|
[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. Zbl 0426.05034, MR 0561047 |
| Reference:
|
[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. Zbl 0792.05050, MR 1110802, 10.1111/j.1749-6632.1989.tb16384.x |
| Reference:
|
[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. Zbl 1289.05057, MR 2986488 |
| Reference:
|
[6] Comellas, F., Gago, S.: Spectral bounds for the betweenness of a graph.Linear Algebra Appl. 423 (2007), 74-80. Zbl 1114.05058, MR 2312324, 10.1016/j.laa.2006.08.027 |
| Reference:
|
[7] Diestel, R.: Graph Theory.Graduate Texts in Mathematics 173, Springer, Berlin (2010). Zbl 1204.05001, MR 2744811, 10.1007/978-3-662-53622-3 |
| Reference:
|
[8] Freeman, L. C.: A set of measures of centrality based on betweenness.Sociometry 40 (1977), 35-41. 10.2307/3033543 |
| Reference:
|
[9] Gago, S., Hurajová, J. Coroničová, Madaras, T.: On betweenness-uniform graphs.Czech. Math. J. 63 (2013), 629-642. Zbl 1299.05085, MR 3125646, 10.1007/s10587-013-0044-y |
| Reference:
|
[10] Knor, M., Madaras, T.: On farness- and reciprocally-selfcentric antisymmetric graphs.Congr. Numerantium 171 (2004), 173-178. Zbl 1064.05052, MR 2122106 |
| Reference:
|
[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. Zbl 1041.05039, MR 2043804, 10.1016/j.disc.2003.07.004 |
| Reference:
|
[12] Plesník, J.: On the sum of all distances in a graph or digraph.J. Graph Theory 8 (1984), 1-21. Zbl 0552.05048, MR 0732013, 10.1002/jgt.3190080102 |
| Reference:
|
[13] Weisstein, E. W.: Generalized Petersen Graph.From MathWorld---A Wolfram Web Resource available at http://mathworld.wolfram.com/GeneralizedPetersenGraph.html. |
| . |
