| Title:
|
On betweenness-uniform graphs (English) |
| Author:
|
Gago, Silvia |
| Author:
|
Coroničová Hurajová, Jana |
| Author:
|
Madaras, Tomáš |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
63 |
| Issue:
|
3 |
| Year:
|
2013 |
| Pages:
|
629-642 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
betweenness centrality |
| Keyword:
|
betweenness-uniform graph |
| MSC:
|
05C12 |
| idZBL:
|
Zbl 06282102 |
| idMR:
|
MR3125646 |
| DOI:
|
10.1007/s10587-013-0044-y |
| . |
| Date available:
|
2013-10-07T12:00:05Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143481 |
| . |
| Reference:
|
[1] Comellas, F., Gago, S.: Spectral bounds for the betweenness of a graph.Linear Algebra Appl. 423 (2007), 74-80. Zbl 1114.05058, MR 2312324 |
| Reference:
|
[2] Diestel, R.: Graph Theory. Transl. from the German. Graduate Texts in Mathematics 173.Springer New York (1997). MR 1448665 |
| Reference:
|
[3] Everett, M. G., Borgatti, S. P.: Ego network betweenness.Social Networks 27 (2005), 31-38. 10.1016/j.socnet.2004.11.007 |
| Reference:
|
[4] Everett, M. G., Sinclair, P., Dankelmann, P.: Some centrality results---new and old.J. Math. Sociol. 28 (2004), 215-227. Zbl 1134.91576, 10.1080/00222500490516671 |
| Reference:
|
[5] Freeman, L. C.: A set of measures of centrality based on betweenness.Sociometry 40 (1977), 35-41. 10.2307/3033543 |
| Reference:
|
[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. |
| Reference:
|
[7] Gago, S., Hurajová, J., Madaras, T.: Notes on the betweenness centrality of a graph.Math. Slovaca 62 (2012), 1-12. MR 2886647, 10.2478/s12175-011-0065-7 |
| Reference:
|
[8] Gethner, E., Sulanke, T.: Thickness-two graphs. II: More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs.Graphs Comb. 25 (2009), 197-217. Zbl 1223.05195, MR 2511878, 10.1007/s00373-008-0833-5 |
| Reference:
|
[9] Newman, M. E. J., Girvan, M.: Finding and evaluating community structure in networks.Phys. Rev. E 69 (2004). MR 2282139 |
| Reference:
|
[10] Phelps, K. T.: Latin square graphs and their automorphism groups.Ars Comb. 7 (1979), 273-299. Zbl 0421.05036, MR 0539719 |
| Reference:
|
[11] Sinclair, P.: Betweenness centralization for bipartite graphs.J. Math. Sociol. 29 (2005), 25-31. Zbl 1079.05517, 10.1080/00222500590889730 |
| Reference:
|
[12] : http://cs.anu.edu.au/~bdm/data/graphs.html.. |
| . |
