1 Introduction and Definitions
There are many complex networks that play a key role in our society. Wellknown examples include the Internet, systems of roads or railroads, electricity networks or social networks. In such networks, it is often the case that information, people or goods travel between different parts of the network, usually using shortest paths between points. From such perspective, points with high throughput are the most important, valuable and often also the most vulnerable parts of the network. Evaluating importance of nodes via their ability to provide information transfer might help in various application areas such as the human brain [sporns] or in construction of utilized algorithms such as community detection algorithms [newman].
A network can be viewed as a graph with vertex set of size and edge set that has maximal degree and minimal degree . Subset of vertices is called a vertex cut, if is disconnected. Vertex connectivity of , , is minimal size of a vertex cut in . We say that is connected if and always remains connected after the removal of less than vertices. For a vertex , stands for the set of all vertices adjacent to . For two vertices , the length of the shortest path is their distance . Diameter of a graph is then . We denote the set by . We use to denote pairs of vertices from the set .
A network centrality measure is a tool helping us to assess how important are nodes in the network. For a connected graph, the betweenness centrality is the following centrality measure evaluating the importance of a vertex based on the amount of shortest paths going through it:
where denotes the number of shortest paths between and and denotes the number of shortest paths between and passing through [freeman].
Note that we count over each (unordered) pair only once. It would be possible to count each pair both as and as . In such case we would obtain the betweenness value that is two times larger than in the unordered version. Similarly, we can define betweenness centrality for an edge in a connected graph:
where is the number of shortest paths between and passing through edge . Note that for every , as the edge always forms the shortest path between its endpoints.
There is a close relationship between betweenness centrality of edges and vertices. By summing up the edge betweenness of all edges incident with a vertex we obtain the adjusted betweenness centrality of this vertex. Relation between normal and adjusted betweenness of a vertex is
(1) 
as has been shown by Caporossi, Paiva, Vukicevic and Segatto [Caporossi2012].
Betweenness centrality is frequently used in applications, even to identify influential patients in the transmission of infection of SARSCoV2 [covid]. It is often studied from the algorithmic point of view [apxalg, algorithm]. Betweenness centrality and its variants are also studied from the graphtheoretical perspective [bcvariant, Barthelemy2018, balancedworkload, graphclasses, adjusted, amalgamation]. In this paper we focus on graphs having the same betweenness on all vertices initiated in studies [GagoCoronicovaHurajovaMadaras2013, CoronicovaHurajovaMadaras2018].
A betweennessuniform graph is a graph, in which all vertices have the same value of betweenness centrality. Thus, betweennessuniform graphs are graphs with all vertices being equally important in terms of the (weighted) number of shortest paths on which they are lying. Networks having this property (or being close to it), are more robust and resistant to attacks, which causes betweennessuniformity to be a promising feature for infrastructural applications. Moreover, betweennessuniform graphs are also interesting from theoretical point of view. When studying the distribution of betweenness in a graph, betweennessuniform graphs are one of the two possible extremal cases and have been already studied by Gago, HurajováCoroničová and Madaras [GagoCoronicovaHurajovaMadaras2013, CoronicovaHurajovaMadaras2018]. The other extremal case are graphs where each vertex has a unique value of betweenness, which were studied by Florez, Narayan, Lopez, Wickus and Worrell [Florez2017].
The class of betweennessuniform graphs includes all vertextransitive graphs, which are graphs with the property that for every pair of vertices there exists an automorphism, which maps one onto the other. It is easy to see that vertextransitive graphs are betweennessuniform. Similarly, edgetransitive graphs are graphs with the property that for each pair of edges there exists an automorphism of the graph mapping one edge onto the other.
Observation 1.1 (Pokorná, 2020 [Pokorna2020])
An edgetransitive graph is betweennessuniform if and only if it is regular.
Proof
We can easily see that edgetransitive graphs are edge betweennessuniform. The result follows from relation (1).
There are also betweennessuniform graphs which are neither vertex nor edgetransitive. A construction of Gago, HurajováCoroničová and Madaras [GagoCoronicovaHurajovaMadaras2013] shows that, for large enough, there are superpolynomially many of these graphs of order . Also, all distanceregular graphs are betweennessuniform [GagoCoronicovaHurajovaMadaras2013]. Apart from the above mentioned results, not much is known about characterisation of betweennessuniform graphs.
In this paper we prove two conjectures stated by HurajováCoroničová and Madaras [CoronicovaHurajovaMadaras2018]. The first one is about the connectivity of betweennessuniform graphs. Having a connected betweennessuniform graph, it is not too hard to show that there cannot be any vertex cut of size one. Consider connected components created by removing a cut vertex . When we consider a vertex for some , only pairs of vertices from contribute to the betweenness of this vertex. On the other hand, all pairs of vertices such that and for contribute to betweenness of the vertex . Using these two observations, along with some general bounds, we get the following property.
Theorem 1.2 (Gago, HurajováCoroničová and Madaras, 2013 [GagoCoronicovaHurajovaMadaras2013])
Any connected betweennessuniform graph is connected.
As we have mentioned above, vertextransitive graphs are betweennessuniform. Thus, all cycles are betweennessuniform. In this paper we show that cycles are the only betweennessuniform graphs which are not connected, as has been conjectured by HurajováCoroničová and Madaras [CoronicovaHurajovaMadaras2018].
Theorem 1.3
If is a connected betweennessuniform graph then it is a cycle or a connected graph.
A variant of this theorem has already been proven for vertextransitive graphs and for regular edgetransitive graphs [Pokorna2020]. Note that there exists a betweennessuniform graph, which is connected and is not vertextransitive, see Figure 1. This implies that we cannot generalize this result to claim that all betweennessuniform graphs are either vertextransitive or connected.
The second conjecture of HurajováCoroničová and Madaras [CoronicovaHurajovaMadaras2018] proven in the following theorem gives a relation between the maximum degree and the diameter of a betweennessuniform graph.
Theorem 1.4
If is betweennessuniform graph and , then .
2 Proof of Theorem 1.3
Before we start with the proof, we introduce some definitions and notation. Betweenness centrality of a vertex induced by a subset of vertices of a graph is defined as
Average betweenness of in is
Average betweenness of induced by is defined analogically as
The main idea of the proof is to take a graph with vertex cut of size two and show that it is not betweennessuniform, unless it is isomorphic to a cycle. We denote to be the cut of size two in minimizing the size of the smallest connected component of , which is denoted by . Let and be the subgraph of induced by .
Observation 2.1
One of the following two cases always happens:
 Case A:

 Case B:

both have at least two neighbours in .
Proof
Suppose that say has only one neighbour in while . Then together with forms a cut of such that , the smallest component of , is smaller than . This is a contradiction with our choice of and .
There might exist one or more connected components in a graph , denoted by . We denote . If contains more connected components , we consider a graph for each of the components separately. The case when is not connected is discussed in Section 2.3. Note that each component of is connected, so is a connected graph. We use and for simplicity in the text below.
Throughout the proof, we use a notion based on a trivial observation below.
Observation 2.2
In a betweennessuniform graph,
for any
Proof
Average betweenness of any two sets of vertices is the same because the betweenness value is the same for all vertices.
A discrepancy between the average betweenness of the vertices of the cut and of the vertices in component is defined as
Let us define
for . We split the discrepancy according to which pairs of vertices contribute to it. Namely,
(2) 
where , resp. , denotes pairs of vertices with both vertices taken from , resp. , and denotes pairs with one vertex from and the second from .
Using Observation 2.1, we are going to show that if and , then the discrepancy is always strictly positive and that discrepancy is zero in the case if and only if is isomorphic to a cycle.
2.1 Vertices of the Cut Have at Least Two Neighbours in
In this section, we count the discrepancy according to equation (2) and show that it is always strictly positive if the cutvertices and have at least two neighbours in , which is Case B of Observation 2.1.
2.1.1 Counting
We take any pair of vertices from and examine how the shortest path between them influences the discrepancy. Basically, there are three different types of shortest paths between and .

The shortest path between and passes only through vertices of . In this case, the shortest path does not influence the discrepancy, because it does not contribute to the average betweenness of either or .

The shortest path between and passes through , especially it enters by one cut vertex and leaves through the second cut vertex. This path always adds one to . If the path passes through all vertices of , then it also adds one to . Otherwise it contributes less than one to . Overall, such paths contribute to the discrepancy by a nonnegative term.

The shortest path between and passes through or without visiting component . This adds something to and nothing to and thus makes a positive contribution to the discrepancy.
Overall, we get that .
For the counting of and we will make use of the following observation about connectivity of and of two lemmas.
Observation 2.3
Connected component is connected.
Proof
Let us assume that there is a vertex cut of size one in . Observe that is also a cut of size one in , because otherwise would separate from and would be also a cut of , which is a contradiction with being connected.
Let such that are connected components of . Two situations can occur.
In the first situation, there exists a vertex of , for example , for which there exists , such that . Let and . We can observe that is a vertex cut of with the property that the smallest component of is smaller than , which is a contradiction with the choice of . This situation is shown in Figure 3.
In the second situation, both and have at least one neighbour in each component of . In this case it is clear that is connected.
The observation above allows us to use the following lemma giving a bound on average distance to a vertex in a connected graph.
Lemma 2.4
Let be a connected graph on vertices and .

for even,

for odd,
and equality is obtained for isomorphic to a cycle.
Note that this result, although in a slightly less precise formulation, was also independently given by Plesník in 1984. [Plesnik]
Proof
We take the longest cycle in containing . Let . We can observe that the (nondecreasing) sequence of distances from to the other vertices of has one of the following forms:

For odd, the sequence is

For even, the sequence is
From the connectivity, each vertex in lies on a cycle containing . Furthermore, from the choice of , so . We get that the sum of distances to in is upper bounded by the sum
for odd and by the sum
for even, because the distances between and vertices on are upper bounded by the sequences mentioned above and distance between and any other vertex in is at most . The sum is maximized when , in which case it is for even, and for odd. The first part of the lemma follows. Since the above sequences contain the distances in a cycle, the second part of the lemma also holds.
Note that by multiplying this result by the number of vertices we obtain a bound on the sum of distances to a fixed vertex in . By multiplying the result by we obtain a bound on the total sum of distances in where we count and as two distinct values. The latter bound can be further used in the following lemma, which gives a direct relation between average betweenness and average distance in a graph.
Lemma 2.5 (Comellas, Gago, 2007 [avgdistbc])
For a graph of order ,
Now the ground is set for the calculation of the remaining two parts of discrepancy.
2.1.2 Counting
Using Observation 2.3 and Lemma 2.4 we obtain that the sum of the lengths of all shortest paths from a fixed vertex in is . Moreover, by multiplying the sum of shortest paths from a fixed vertex by the number of vertices in , we obtain that the sum of all shortest paths in is at most .
To obtain an upper bound on , we utilize the relation from Lemma 2.5, using the sum of distances in , but as the number of vertices. This corresponds to dividing all the contributions of shortest paths in only to vertices of . Note that some of the shortest paths might pass though or , but this can only decrease the average betweenness of . As a result,
Finally, we assume that to obtain a a lower bound on the discrepancy. This results in
2.1.3 Counting
Clearly, each path from to passes through at least one vertex of the cut , adding at least to . As a result, .
Now we show an upper bound on the average betweenness of .
Observation 2.6
Let and suppose . The contribution of to is maximized, when all paths from to pass through .
Proof
Otherwise, there exists such that the shortest path between and passes through . This means that . Together with , we get , so the path passes through smaller or the same number of vertices of , than it would if it went through . See Figure 4 for illustration.
From now on, we assume that for each there exists such that all paths from to are passing through and we denote .
We can use Lemma 2.4 and the fact that is connected to obtain that This corresponds to a sum of distances travelled inside by all paths from to a fixed . Note that for any , the sum of contributions of all paths of length to the betweenness of is and thus
When we take the lower bound on and upper bound on we can bound the discrepancy
Together we obtain
which holds for ; and . It remains to discuss the cases and .
For and we have used the database provided by Brendan McKay [smallgraphs] to filter all betweennessuniform graphs up to ten vertices and verify that the theorem holds for all such graphs. For the case we have used the program nauty [nauty] to generate all connected graphs on vertices as choices for and all connected graphs on seven vertices as choices of and for all choices of , and their possible adjacencies in verified the theorem on graphs of this form.
We have seen that discrepancy is always greater than zero if and , implying is not betweennessuniform in this case. From this fact and Observation 2.1, we see that the size of the minimal connected component must be one if the connected graph is betweennessuniform.
2.2 Component Consists of a Single Vertex
Here we consider the Case A from Observation 2.1 giving which means that contains a vertex of degree for which . Let and let .
Let us recall that discrepancy is defined as , which in the case considered in this section equals to . Also note that in this case , where equality is obtained when is the single shortest path between and . Similarly to the previous section, we will decompose discrepancy to two parts, one part induced by the pairs of vertices from and second part induced by pairs where at least one vertex is part of :
Observe that because every (shortest) path between two vertices of going through the vertex of must contain both and . This enables us to focus only on paths with at least one endvertex in the set .
We start with the following observation, which enables us to rule out the case .
Observation 2.7
A betweennessuniform graph of order has the values of betweenness centrality equal to zero if and only if is isomorphic to .
Proof
It has been already shown that a vertex has betweenness value zero if and only if it’s neighborhood forms a clique. [EverettSeidman1985], [Grassietal2009] It is clear that neighborhood of each vertex in forms a clique and thus is betweennessuniform with betweenness value zero.
Suppose we have a betweennessuniform graph with betweenness value zero where exist such that . If there are more missing edges, take whose distance is minimal. If , then exists on a shortest path between and such that and . As a result, and thus exists such that . However, , so , a contradiction.
Observe that if contains the edge , then there is no shortest path passing through and thus . As a consequence of Observation 2.7, is isomorphic to . Therefore, we assume that does not contain the edge from now on. Let be the shortest path from to in .
Now, the main goal is to show that there exists a vertex (almost) in the middle of the path , which is a vertexcut of .
Lemma 2.8
There exists such that and is a vertexcut of .
Proof
For a vertex in , set . Let be the number of vertices of different from and . Along the path from to , the function consecutively gets values . It follows that, depending on the parity of , one of the following two cases happens:
 Case 1:

There are two consecutive vertices on such that
 Case 2:

There are three consecutive vertices on such that
Before considering Cases 1 and 2 separately, we prove the following proposition.
Proposition 2.9
Let .
 (i)

If , then
 (ii)

If , then
 (iii)

If , then
 (iv)

If , then
Proof
 (i)

If , then all shortest paths from to avoid as well as and all shortest paths from to avoid and . Hence, shortest paths from to do not contribute to the betweenness of vertices and . Every shortest path from to goes through exactly one of the vertices and . Part (i) of the proposition follows.
 (ii)

If , then is closer to than to and thus every shortest path from to avoids and . For the same reason, every shortest path from to visits and avoids , so the total contribution of these paths is .
There are two types of shortest paths between and . First type passes through both and , second type avoids both of them. As , the number of shortest paths of the first type is the same as , the total number of shortest paths from to . As a result, exactly of the shortest paths from to visit and . Each of these paths contributes one to and , which means it contributes one half to . As a result, the contribution of each of these paths to the discrepancy is . Note that , because each shortest path from to can be extended by and to a shortest path between and . Also, there must be at least one shortest path avoiding and .
All the other shortest paths from to avoid both and , so they do not influence the discrepancy. Part (ii) follows.
 (iii)

Analogous to the proof of part (ii), with the roles of and exchanged.
 (iv)

If then is much closer to than to , so all shortest paths from to visit none of the vertices and , which does not influence discrepancy. Also, all shortest paths from to visit and do not visit , contributing to , and all shortest paths from to visit both and , contributing to and to . Note that each shortest path can be uniquely extended to a shortest path, so the number of these paths is the same. Part (iv) then follows.
The case is analogous, with the roles of and exchanged.
Now we continue with the proof of Lemma 2.8. Suppose that Case 1 holds. According to Proposition 2.9 (i),
Further, we have , since the only shortest path between and goes through . Proposition 2.9 now implies that if then every vertex in satisfies . Since the function differs by at most two on any pair of neighbors in , and are cuts of . This finishes the proof of Lemma 2.8 for Case 1.
Suppose now that Case 2 happens. We have , because the for and otherwise it is . According to Proposition 2.9 (i), . According to Proposition 2.9 (ii),(iii),
which is positive. It now follows from Proposition 2.9 (i) that for every vertex , since otherwise .
We have , because each shortest path can be extended by and to a shortest path and each shortest path can be extended by and to a shortest path. This holds because . The equality is obtained if and only if all shortest paths from to go either through or . Similarly, . Thus,
Proposition 2.9 now implies that if then every vertex in satisfies . It follows that are cuts in .
This finishes the proof of Lemma 2.8 for Case 2.
Now we use Lemma 2.8 to show that if in with a cut such that is the smallest component of , is either isomorphic to a cycle, or not betweennessuniform. The latter will be done by showing .
If is isomorphic to a cycle, then it fulfills the condition of Theorem 1.3 and we are done. Suppose is not isomorphic to a cycle and let us take the vertex from Lemma 2.8. The graph consists of two connected components such that . If , we consider and if , we consider . If , .
Since is not a cycle, at least one of the following two conditions is satisfied:

[align=left]
 (C1)

is not a path, or
 (C2)

is not a path.
If both (C1) and (C2) hold, then without loss of generality, we suppose that . Then we consider the graph . If, let us say, (C1) holds and (C2) does not hold, then there is a single shortest path from to . It follows that , since otherwise , forms a path, is not a path and thus . We now can again consider the graph .
If is connected, we can continue in the same way as in Case B of the Observation 2.1, which always yields positive discrepancy as has been shown in previous subsection. Note that this is possible as we have only used the fact that is the smallest component of to deduce that it is connected.
If is not connected, there is a cut vertex of . Recall that in order to be betweennessuniform, must be connected and thus it also holds that separates and . Let and be the two connected components of , where and . Since is not a path from to , at least one of the two subgraphs of induced by and by , respectively, is not a path from to and from to , respectively. We consider such a subgraph and check again if it is connected. Continuing this process, due to the connectivity of , we end up with a cut of which cuts off a connected component, which is a subgraph of . Then we can continue as in Case B of Observation 2.1 which leads to and thus is not betweennessuniform. This finishes the proof of Theorem 1.3 for Case A of Observation 2.1.
2.3 There are More Connected Components in
If had only one connected component , as we have assumed in the previous parts of this section, we are finished. Otherwise, we know that and any has either positive discrepancy, or it is isomorphic to a cycle. We can observe that for and with positive discrepancy,
has also positive discrepancy. This follows from the fact that whenever we obtain positive discrepancy, it is due to the Case B of Observation 2.1, which has been solved in Subsection 2.1. From there, it is clear that discrepancy rises with growing difference between and . The only case when discrepancy is zero for each is when each is isomorphic to a path between and . Recall that , because any path between vertices of passing through also passes through both and . Suppose and for any two connected components of . Then the shortest path between and passes through and avoids , making , which leads to .
By the results above, any connected graph has either , implying it is not betweennessuniform, or it has and is isomorphic to a cycle. This finishes the proof of Theorem 1.3.
3 Relation between Maximal Degree and Diameter of BetweennessUniform Graphs
In this section we prove a conjecture of HurajováCoroničová and Madaras [CoronicovaHurajovaMadaras2018] claiming that betweennessuniform graphs with high maximal degree have small diameter.
Conjecture 3.1 ([CoronicovaHurajovaMadaras2018])
If is a betweennessuniform graph and , then .
In a previous article by Gago, HurajováCoroničová and Madaras [GagoCoronicovaHurajovaMadaras2013], this conjecture has been proved for and and later HurajováCoroničová and Madaras [CoronicovaHurajovaMadaras2018] proved the conjecture for by showing that a betweennessuniform graph with has for .
Before proving Conjecture 3.1, we state the following more general result.
Theorem 3.2
Let be a connected graph with . Then .
Proof
For we have and for we have , so the claim holds for these values of . In the rest of the proof we assume .
Let be a vertex such that and let be a pair of vertices such that . Thus, every path between and has at least vertices. We now show that at least of these vertices do not lie in the set . Let be a path between and . If contains at most five vertices of then it contains at least vertices outside of . Suppose now that contains more than five vertices of . Let be the shortest subpath of covering all the vertices of lying in . Let and denote the endvertices of the path . They both lie in . If is one of the two vertices and then we denote by the path consisting of a single edge . Otherwise we denote by the path . In each case, is a path in containing only vertices of . Now, let be the path between and in obtained from by replacing the subpath by . The path contains at most five vertices of . Therefore, it contains at least vertices not lying in . All these vertices lie also in . This concludes the proof that every path between and has at least vertices not lying in .
As is connected, there are at least vertex disjoint paths between and . They together contain at least vertices not lying in . Since the size of is , we obtain a lover bound on the number of vertices,
giving . Since is an integer, we get .
Corollary 3.3
Let be a connected graph with . Then .
Using Corollary 3.3 and Theorem 1.3, we can obtain a result, which is stronger than Conjecture 3.1 for . For , the conjecture has already been proved, as we have mentioned above, which makes the statement true for all values of .
Corollary 3.4
Let be a betweennessuniform graph with . Then .
Note that the assumption is necessary, because is betweennessuniform, has , implying , and its diameter is at most , which is greater than for .
Proposition 3.5
The bound of Theorem 3.2 is tight for .
Proof
Given and we create a graph containing vertices and in distance that contains vertex disjoint paths of length . We take vertices such that and for , which are the midpoints of the paths. Next we define , respectively
Comments
There are no comments yet.