Geodesic
On betweenness-uniform graphs
Czechoslovak Mathematical Journal, Tome 63 (2013) no. 3, pp. 629-642
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-013-0044-y
Classification : 05C12
Keywords: betweenness centrality; betweenness-uniform graph 
@article{10_1007_s10587_013_0044_y,
     author = {Gago, Silvia and Coroni\v{c}ov\'a Hurajov\'a, Jana and Madaras, Tom\'a\v{s}},
     title = {On betweenness-uniform graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {629--642},
     year = {2013},
     volume = {63},
     number = {3},
     doi = {10.1007/s10587-013-0044-y},
     mrnumber = {3125646},
     zbl = {06282102},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0044-y/}
}
TY  - JOUR
AU  - Gago, Silvia
AU  - Coroničová Hurajová, Jana
AU  - Madaras, Tomáš
TI  - On betweenness-uniform graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2013
SP  - 629
EP  - 642
VL  - 63
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0044-y/
DO  - 10.1007/s10587-013-0044-y
LA  - en
ID  - 10_1007_s10587_013_0044_y
ER  - 
%0 Journal Article
%A Gago, Silvia
%A Coroničová Hurajová, Jana
%A Madaras, Tomáš
%T On betweenness-uniform graphs
%J Czechoslovak Mathematical Journal
%D 2013
%P 629-642
%V 63
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0044-y/
%R 10.1007/s10587-013-0044-y
%G en
%F 10_1007_s10587_013_0044_y
Gago, Silvia; Coroničová Hurajová, Jana; Madaras, Tomáš. On betweenness-uniform graphs. Czechoslovak Mathematical Journal, Tome 63 (2013) no. 3, pp. 629-642. doi: 10.1007/s10587-013-0044-y

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

[2] Diestel, R.: Graph Theory. Transl. from the German. Graduate Texts in Mathematics 173. Springer New York (1997). | MR

[3] Everett, M. G., Borgatti, S. P.: Ego network betweenness. Social Networks 27 (2005), 31-38. | DOI

[4] Everett, M. G., Sinclair, P., Dankelmann, P.: Some centrality results---new and old. J. Math. Sociol. 28 (2004), 215-227. | DOI | Zbl

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

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

[7] Gago, S., Hurajová, J., Madaras, T.: Notes on the betweenness centrality of a graph. Math. Slovaca 62 (2012), 1-12. | DOI | MR

[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. | DOI | MR | Zbl

[9] Newman, M. E. J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69 (2004). | MR

[10] Phelps, K. T.: Latin square graphs and their automorphism groups. Ars Comb. 7 (1979), 273-299. | MR | Zbl

[11] Sinclair, P.: Betweenness centralization for bipartite graphs. J. Math. Sociol. 29 (2005), 25-31. | DOI | Zbl

[12] http://cs.anu.edu.au/~bdm/data/graphs.html</b>

Cité par Sources :