Geodesic
More on betweenness-uniform graphs
Czechoslovak Mathematical Journal, Tome 68 (2018) no. 2, pp. 293-306 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2018.0087-16
Classification : 05C15
Keywords: betweenness centrality; betweenness-uniform graph 
@article{10_21136_CMJ_2018_0087_16,
     author = {Coroni\v{c}ov\'a Hurajov\'a, Jana and Madaras, Tom\'a\v{s}},
     title = {More on betweenness-uniform graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {293--306},
     year = {2018},
     volume = {68},
     number = {2},
     doi = {10.21136/CMJ.2018.0087-16},
     mrnumber = {3819175},
     zbl = {06890374},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0087-16/}
}
TY  - JOUR
AU  - Coroničová Hurajová, Jana
AU  - Madaras, Tomáš
TI  - More on betweenness-uniform graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2018
SP  - 293
EP  - 306
VL  - 68
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0087-16/
DO  - 10.21136/CMJ.2018.0087-16
LA  - en
ID  - 10_21136_CMJ_2018_0087_16
ER  - 
%0 Journal Article
%A Coroničová Hurajová, Jana
%A Madaras, Tomáš
%T More on betweenness-uniform graphs
%J Czechoslovak Mathematical Journal
%D 2018
%P 293-306
%V 68
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0087-16/
%R 10.21136/CMJ.2018.0087-16
%G en
%F 10_21136_CMJ_2018_0087_16
Coroničová Hurajová, Jana; Madaras, Tomáš. More on betweenness-uniform graphs. Czechoslovak Mathematical Journal, Tome 68 (2018) no. 2, pp. 293-306. doi: 10.21136/CMJ.2018.0087-16

[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 | MR | JFM

[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 | MR | JFM

[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 | JFM

[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 | MR | JFM

[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 | JFM

[6] Comellas, F., Gago, S.: Spectral bounds for the betweenness of a graph. Linear Algebra Appl. 423 (2007), 74-80. | DOI | MR | JFM

[7] Diestel, R.: Graph Theory. Graduate Texts in Mathematics 173, Springer, Berlin (2010). | DOI | MR | JFM

[8] Freeman, L. C.: A set of measures of centrality based on betweenness. Sociometry 40 (1977), 35-41. | DOI

[9] Gago, S., Hurajová, J. Coroničová, Madaras, T.: On betweenness-uniform graphs. Czech. Math. J. 63 (2013), 629-642. | DOI | MR | JFM

[10] Knor, M., Madaras, T.: On farness- and reciprocally-selfcentric antisymmetric graphs. Congr. Numerantium 171 (2004), 173-178. | MR | JFM

[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 | MR | JFM

[12] Plesník, J.: On the sum of all distances in a graph or digraph. J. Graph Theory 8 (1984), 1-21. | DOI | MR | JFM

[13] Weisstein, E. W.: Generalized Petersen Graph. From MathWorld---A Wolfram Web Resource available at http://mathworld.wolfram.com/GeneralizedPetersenGraph.html

Cité par Sources :