Proposition For each rational number $c=\frac{p}{q}$ we can construct a graph $G_c$, which contains vertex $v$ such that $C_B(v)=c$.
Construction of a graph $G_c$ Let us have disjoint union of
- $K_p, K_{q−1}$ and edge $\{u,v\}$
- $u$ connect to $K_p$ and $v$ with $K_{q−1}$
- make a full join of $K_p$ and $K_{q−1}$
Automorphism group $Aut(G)$ is a set of bijections $\sigma:V \rightarrow V$, which preserve edges. Centrality values are preserved by automorphism group.
Graph $G$ is betweenness uniform, if $C_B(v) = C_B(u) \forall u,v \in V(G)$.
Graph $G$ is vertex transitive, if $\forall x,y \in V(G)$ exists automorphism $\sigma$ mapping $x \rightarrow y$. From this trivially follows $C_B(x)=C_B(y)$, so
Observation Vertex transitive graphs are betweenness uniform.
Remark: There are betweenness uniform graphs, which are neither vertex transitive nor regular.
Proposition Assume $G$ is betweenness uniform graph and let $G'$ be a graph, which is created by
- substituing each vertex $v$ with a complete graph $K_a$ for some natural $a$, whose vertices we denote by $v_1, \dots,v_a$, and
- adding $(v_i,u) \in E(G')$ for all $i \in [a]$ whenever $(v,u) \in E(G)$.
Then $G'$ is also betweenness uniform.
Task 1: Implement function is_betweenness_uniform(G), which checks for given graph, whether it is or is not betweenness uniform. Download list of all betweenness uniform grpahs on at most 10 vertices: https://iuuk.mff.cuni.cz/~anet/grafy-a-site/bugs.g6
Use your function to verify that these graphs are really betweenness uniform.
From the lecture (and last tutorial) we know that large group of betweenness uniform graphs are vertex transitive graphs. Testing of this property is a little more complicated and package NetworkX does not support it. Checking vertex transitivity and other algebraic operations on graphs, such as counting automorphism group, are implemented in SageMath(shortly Sage):https://doc.sagemath.org/html/en/index.html
Sage is quite large piece of a mathematical software. It is easier to run Python inside Sage by command sage -python <skript>.py than to import Sage into Python. In your script you can easily put line from sage.all import * and use all functions implemented inside SageMath.
Manual for installing SageMath is here: https://doc.sagemath.org/html/en/faq/faq-usage.html An alternative to installing Sage is to use it from some online environment, such as https://cocalc.com or https://sagecell.sagemath.org/.
Back to testing vertex transitivity. Sage contains for object Graph(from Sage, not from NetworkX!) a method is_vertex_transitive(). Specific way to call this method and optional parameters are listed in the documentation: https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.is_vertex_transitive
Task 2: Find out using Sage whose betweenness uniform graphs from previous task are not vertex transitive. Furthermore, whose graphs are not even regular? Take a look at the resulting graphs.
We start by checking vertex transitivity using python inside sage and saving the nontransitive graphs into non-vt-bugs.g6:
Task 3: Implement function, which for given $c=\frac{p}{q}$ constructs a graph containing a vertex $v$ for which $C_B(v)=\frac{p}{q}$.
Task 4: Implement function blow-up(G, a) which returns for a graph $G$ the construction from the proposition, where $a$ is the size of the cliques. Check the claim of the proposition by checking betweenness uniformity of the resulting graph for several betweenness uniform input graphs.