On betweenness-uniform graphs

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

Czechoslovak Mathematical Journal (2013)

  • Volume: 63, Issue: 3, page 629-642
  • ISSN: 0011-4642

Abstract

top
The betweenness centrality of a vertex of a graph is the fraction of shortest paths between all pairs of vertices passing through that vertex. In this paper, we study properties and constructions of graphs whose vertices have the same value of betweenness centrality (betweenness-uniform graphs); we show that this property holds for distance-regular graphs (which include strongly regular graphs) and various graphs obtained by graph cloning and local join operation. In addition, we show that, for sufficiently large n , there are superpolynomially many betweenness-uniform graphs on n vertices, and explore the structure of betweenness-uniform graphs having a universal or sub-universal vertex.

How to cite

top

Gago, Silvia, Coroničová Hurajová, Jana, and Madaras, Tomáš. "On betweenness-uniform graphs." Czechoslovak Mathematical Journal 63.3 (2013): 629-642. <http://eudml.org/doc/260632>.

@article{Gago2013,
abstract = {The betweenness centrality of a vertex of a graph is the fraction of shortest paths between all pairs of vertices passing through that vertex. In this paper, we study properties and constructions of graphs whose vertices have the same value of betweenness centrality (betweenness-uniform graphs); we show that this property holds for distance-regular graphs (which include strongly regular graphs) and various graphs obtained by graph cloning and local join operation. In addition, we show that, for sufficiently large $n$, there are superpolynomially many betweenness-uniform graphs on $n$ vertices, and explore the structure of betweenness-uniform graphs having a universal or sub-universal vertex.},
author = {Gago, Silvia, Coroničová Hurajová, Jana, Madaras, Tomáš},
journal = {Czechoslovak Mathematical Journal},
keywords = {betweenness centrality; betweenness-uniform graph; betweenness centrality; betweenness-uniform graph},
language = {eng},
number = {3},
pages = {629-642},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On betweenness-uniform graphs},
url = {http://eudml.org/doc/260632},
volume = {63},
year = {2013},
}

TY - JOUR
AU - Gago, Silvia
AU - Coroničová Hurajová, Jana
AU - Madaras, Tomáš
TI - On betweenness-uniform graphs
JO - Czechoslovak Mathematical Journal
PY - 2013
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 63
IS - 3
SP - 629
EP - 642
AB - The betweenness centrality of a vertex of a graph is the fraction of shortest paths between all pairs of vertices passing through that vertex. In this paper, we study properties and constructions of graphs whose vertices have the same value of betweenness centrality (betweenness-uniform graphs); we show that this property holds for distance-regular graphs (which include strongly regular graphs) and various graphs obtained by graph cloning and local join operation. In addition, we show that, for sufficiently large $n$, there are superpolynomially many betweenness-uniform graphs on $n$ vertices, and explore the structure of betweenness-uniform graphs having a universal or sub-universal vertex.
LA - eng
KW - betweenness centrality; betweenness-uniform graph; betweenness centrality; betweenness-uniform graph
UR - http://eudml.org/doc/260632
ER -

References

top
  1. Comellas, F., Gago, S., Spectral bounds for the betweenness of a graph, Linear Algebra Appl. 423 (2007), 74-80. (2007) Zbl1114.05058MR2312324
  2. Diestel, R., Graph Theory. Transl. from the German. Graduate Texts in Mathematics 173, Springer New York (1997). (1997) MR1448665
  3. Everett, M. G., Borgatti, S. P., 10.1016/j.socnet.2004.11.007, Social Networks 27 (2005), 31-38. (2005) DOI10.1016/j.socnet.2004.11.007
  4. Everett, M. G., Sinclair, P., Dankelmann, P., 10.1080/00222500490516671, J. Math. Sociol. 28 (2004), 215-227. (2004) Zbl1134.91576DOI10.1080/00222500490516671
  5. Freeman, L. C., 10.2307/3033543, Sociometry 40 (1977), 35-41. (1977) DOI10.2307/3033543
  6. Gago, S., Métodos Espectrales y Nuevas Medidas Modelos y Parámetros en Grafos Pequeño-mundo Invariantes de escala, Ph.D. Thesis Univ. Politècnica de Catalunya, Barcelona (2006), Spanish. (2006) 
  7. Gago, S., Hurajová, J., Madaras, T., 10.2478/s12175-011-0065-7, Math. Slovaca 62 (2012), 1-12. (2012) MR2886647DOI10.2478/s12175-011-0065-7
  8. Gethner, E., Sulanke, T., 10.1007/s00373-008-0833-5, Graphs Comb. 25 (2009), 197-217. (2009) Zbl1223.05195MR2511878DOI10.1007/s00373-008-0833-5
  9. Newman, M. E. J., Girvan, M., Finding and evaluating community structure in networks, Phys. Rev. E 69 (2004). (2004) MR2282139
  10. Phelps, K. T., Latin square graphs and their automorphism groups, Ars Comb. 7 (1979), 273-299. (1979) Zbl0421.05036MR0539719
  11. Sinclair, P., 10.1080/00222500590889730, J. Math. Sociol. 29 (2005), 25-31. (2005) Zbl1079.05517DOI10.1080/00222500590889730
  12. http://cs.anu.edu.au/~bdm/data/graphs.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.