More on betweenness-uniform graphs

Jana Coroničová Hurajová; Tomáš Madaras

Czechoslovak Mathematical Journal (2018)

  • Volume: 68, Issue: 2, page 293-306
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Coroničová Hurajová, Jana, and Madaras, Tomáš. "More on betweenness-uniform graphs." Czechoslovak Mathematical Journal 68.2 (2018): 293-306. <http://eudml.org/doc/294763>.

@article{CoroničováHurajová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.},
author = {Coroničová Hurajová, Jana, Madaras, Tomáš},
journal = {Czechoslovak Mathematical Journal},
keywords = {betweenness centrality; betweenness-uniform graph},
language = {eng},
number = {2},
pages = {293-306},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {More on betweenness-uniform graphs},
url = {http://eudml.org/doc/294763},
volume = {68},
year = {2018},
}

TY - JOUR
AU - Coroničová Hurajová, Jana
AU - Madaras, Tomáš
TI - More on betweenness-uniform graphs
JO - Czechoslovak Mathematical Journal
PY - 2018
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 68
IS - 2
SP - 293
EP - 306
AB - 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.
LA - eng
KW - betweenness centrality; betweenness-uniform graph
UR - http://eudml.org/doc/294763
ER -

References

top
  1. Akiyama, J., Ando, K., Avis, D., 10.1016/S0304-0208(08)72802-0, Convexity and Graph Theory Proc. Conf., Jerusalem, 1981, Ann. Discrete Math. 20; North-Holland Mathematics Studies 87, North-Holland, Amsterdam (1984), 13-23. (1984) Zbl0566.05053MR0791008DOI10.1016/S0304-0208(08)72802-0
  2. Balakrishnan, K., Changat, M., Peterin, I., Špacapan, S., Šparl, P., Subhamathi, A. R., 10.1016/j.ejc.2008.09.018, Eur. J. Comb. 30 (2009), 1048-1053. (2009) Zbl1185.05052MR2513907DOI10.1016/j.ejc.2008.09.018
  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. (1979) Zbl0426.05034MR0561047
  4. Buckley, F., 10.1111/j.1749-6632.1989.tb16384.x, Proc. Conf., Jinan, 1986 Ann. N. Y. Acad. Sci. 576, New York Academy of Sciences, New York (1989), 71-78. (1989) Zbl0792.05050MR1110802DOI10.1111/j.1749-6632.1989.tb16384.x
  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. (2012) Zbl1289.05057MR2986488
  6. Comellas, F., Gago, S., 10.1016/j.laa.2006.08.027, Linear Algebra Appl. 423 (2007), 74-80. (2007) Zbl1114.05058MR2312324DOI10.1016/j.laa.2006.08.027
  7. Diestel, R., 10.1007/978-3-662-53622-3, Graduate Texts in Mathematics 173, Springer, Berlin (2010). (2010) Zbl1204.05001MR2744811DOI10.1007/978-3-662-53622-3
  8. Freeman, L. C., 10.2307/3033543, Sociometry 40 (1977), 35-41. (1977) DOI10.2307/3033543
  9. Gago, S., Hurajová, J. Coroničová, Madaras, T., 10.1007/s10587-013-0044-y, Czech. Math. J. 63 (2013), 629-642. (2013) Zbl1299.05085MR3125646DOI10.1007/s10587-013-0044-y
  10. Knor, M., Madaras, T., On farness- and reciprocally-selfcentric antisymmetric graphs, Congr. Numerantium 171 (2004), 173-178. (2004) Zbl1064.05052MR2122106
  11. Malnič, A., Marušič, D., Potočnik, P., Wang, C., 10.1016/j.disc.2003.07.004, Discrete Math. 280 (2004), 133-148. (2004) Zbl1041.05039MR2043804DOI10.1016/j.disc.2003.07.004
  12. Plesník, J., 10.1002/jgt.3190080102, J. Graph Theory 8 (1984), 1-21. (1984) Zbl0552.05048MR0732013DOI10.1002/jgt.3190080102
  13. Weisstein, E. W., Generalized Petersen Graph, From MathWorld---A Wolfram Web Resource available at http://mathworld.wolfram.com/GeneralizedPetersenGraph.html. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.