On betweenness-uniform graphs

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

Full description

Saved in:
Bibliographic Details
Published in:Czechoslovak mathematical journal 2013-09, Vol.63 (3), p.629-642
Main Authors: Gago, Silvia, Hurajová, Jana Coroničová, Madaras, Tomáš
Format: Article
Language:English
Subjects:
Analysis
Convex and Discrete Geometry
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Ordinary Differential Equations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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 distanceregular 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.
ISSN:0011-4642
1572-9141
DOI:10.1007/s10587-013-0044-y