[Math] Number of paths in hypercube graph

combinatoricsgraph theory

I have seen that the number of node-disjoint, shortest paths (between two vertices) from x to y in hypercube graph is d(x,y). I was wondering is there a way to find and prove the formula for:

1) Maximum number of mutually node-disjoint paths from x to y ? – regardless of their length (upper bound in graph Qn is n, obviously)

2) The number of all paths from x to y ?

EDIT: For the clarification:
x and y are any arbitrary vertices, all paths should be simple.

Best Answer

For the first question, the answer is exactly $n$, regardless of the choice of $x$ and $y$. As you said, clearly there cannot be more than $n$, for the start vertex $x$ only has $n$ neighbours. To see that this is attained, we use Balinski's theorem, which asserts that $Q_n$ is $n$-connected. In other words, for any vertex set $S \subseteq V(Q_n)$ containing at most $n - 1$ vertices, the graph $G \setminus S$ remains connected. Now recall that Menger's theorem gives an equivalent definition of $k$-connectedness: a graph is $k$-connected if and only if there are at least $k$ independent paths between any two of its vertices. Thus, putting these two results together shows that there are $n$ independent paths between any two vertices in $Q_n$.

For the second question, I don't think there is a neat answer. To give you an idea of the complexity of some of the paths that can occur: there exists a Hamiltonian path between any pair of vertices that receive a different colour in the canonical 2-colouring of $Q_n$. This is easily proven by induction:

For $n \leq 2$ you can show this by hand.
For $n > 2$, you partition the hypercube in two (disjoint) hyperfaces $H_x,H_y$, the first one containing $x$ and the second one containing $y$. Furthermore, you choose another vertex $u$ in the hyperface $H_x$ which has the same colour as $y$ (and therefore a different colour from $x$), and you let $v$ be the unique neighbour of $u$ in the hyperface $H_y$. Note that $v$ is necessarily different from $y$, since $v$ has the same colour as $x$. By the induction hypothesis, we can find a Hamiltonian path from $x$ to $v$ that lies entirely in the hyperface $H_x$. Then we cross over to the dark side and find a Hamiltonian path from $v$ to $y$ that lies entirely in the hyperface $H_y$. (These paths exist since $H_x$ and $H_y$ are isomorphic to $Q_{n-1}$.) This gives us a Hamiltonian path from $x$ to $y$.

Thus, there are many, many paths! Indeed, determining the total number seems to be a very hard problem: even for the special case where $x$ and $y$ are opposing corners of the hypercube, OEIS only knows the answer up to $n = 5$ (OEIS sequence A059783).

Note however that the number of shortest paths from $x$ to $y$ is easy to determine. I'll leave this as an exercise. ;-)

Related Solutions

[Math] Disjoint paths in a directed graph

If by "disjoint" you mean "vertex-disjoint", this is false, e.g.:

            +------
            |     |
            |     V
 v1 -> a -> v2 -> c -> v1
 |          ^     |    ^
 |          |     |    |
 +---> b ---+     +----+

(where $v_1$ appears twice for graphical convenience but is the same vertex).

If by "disjoint" you mean "edge-disjoint", this is true. Remove the edges of the $k$ mutually edge-disjoint paths from $v_1$ to $v_2$. Now all vertices still have equal in-degree and out-degree, except $v_1$ has $k$ more edges leading in and $v_2$ has $k$ more edges leading out. Start a path from $v_2$ by taking any of the edges. Whatever vertex you reach via an edge leading to it must have a matching edge leading away from it. Keep following these edges. Eventually you must end up at $v_1$, since there's no other vertex with more edges leading in than out. This completes the first path. Remove its edges and repeat $k-1$ times.

Maximum possible edge betweenness of a graph

Suppose that a shortest path from vertex $v$ to vertex $w$ in the graph uses edge $xy$: let's say the path goes $(v, \dots, x, y, \dots, w)$. Then distances from $v$ are strictly increasing along the path, and distances from $w$ are strictly decreasing: in particular, $d(v,x) < d(v,y)$ and $d(w,x) > d(w,y)$.

This means that all shortest paths using edge $xy$ must start at a vertex closer to $x$ than to $y$, and end at a vertex closer to $y$ than to $x$. If there are $n_x$ vertices of the first type, and $n_y$ of the second, then at most $n_x \cdot n_y$ pairs of vertices have a shortest path using edge $xy$.

With the constraint $n_x + n_y \le n$ and $n_x, n_y \ge 0$, $n_x \cdot n_y$ is maximized at $\lfloor \frac{n^2}{4}\rfloor$ when $n_x = n_y = \frac n2$ (for even $n$) or when $\{n_x, n_y\} = \{\frac{n-1}{2}, \frac{n+1}{2}\}$ (for odd $n$).

This bound is achievable for all $n$, by letting $xy$ be the only edge between two connected subgraphs, one with $n_x$ vertices and one with $n_y$ vertices.

Best Answer

Related Solutions

[Math] Disjoint paths in a directed graph

Maximum possible edge betweenness of a graph

Related Question