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.
We study improper interval edge colourings, defined by the requirement that the edge colours around each vertex form an integer interval. For the corresponding chromatic invariant (being the maximum number of colours in such a colouring), we present upper and lower bounds and discuss their qualities; also, we determine its values and estimates for graphs of various families, like wheels, prisms or complete graphs. The study of this parameter was inspired by the interval colouring, introduced by Asratian, Kamalian (1987). The difference is that we relax the requirement on the original colouring to be proper., Peter Hudák, František Kardoš, Tomáš Madaras, Michaela Vrbjarová., and Obsahuje seznam literatury