Skip to main content
4 of 4
rephrased the question and modified the title
ght
  • 3.6k
  • 1
  • 24
  • 48

Number of Geodesic Paths Passing Through a Vertex in an Expander Graph

Let $\{G_{n}\}$ be a sequence of $k$-regular expander graphs. For each $n$ assume that each pair of nodes in the graph is transmitting a unit load of traffic and the traffic goes through the minimum path between nodes (if there is more than one minimum path we choose one arbitrarily). Then the total traffic in $G_{n}$ is equal to $N(N-1)/2$ where $N=N(n)=|G_{n}|$.

Given a node $v\in G_{n}$ we define $T_{n}(v)$ as the total traffic generated in the graph passing through $v$. In other words, $T_{n}(v)$ is the sum off all the geodesic paths in $G_{n}$ which are carrying traffic and contain the node $v$.

Let $T(G_{n})$ be the maximum load in the graph. More precisely, $$ T(G_{n})=\max_{v\in G_{n}} \{T_{n}(v)\}. $$

As Lukasz pointed out this question can be reformulated without talking about traffic. For instance, for each two vertices we choose a geodesic that connects them and then define $T_{n}(v)$ as the number of geodesics paths that pass through the node $v$.

My question is:

  • What can we say about the rate of growth of $T(G_{n})$?

  • Is there anything known in this direction?

ght
  • 3.6k
  • 1
  • 24
  • 48