Number of sequences of edges that contain at least one subsequence which is a walk between vertex $i$ and $j$

Question

Typically a walk is defined as a vertex-edge sequence, e.g. $(v_1, e_1, v_2, e_2, v_3)$, but suppose we are working in the undirected simple graph setting. Instead, let's say an edge-sequence $(e_1, e_2)$ is a walk from vertex $v_1$ to $v_3$ if we can recover the full vertex-edge sequence definition by inserting vertices into the edge-sequence reasonably, i.e. if a vertex precedes or follows an edge in the sequence it must be incident to that edge. This edge-sequence notation makes things ambiguous in the sense that $(e)$ can represent two walks going in either direction along the edge, but we won't worry about this.

My most general question: For a given graph $G$, is there an efficient way to count the number of edge-sequences of length $k$ that contain at least one subsequence which is a walk from vertex $i$ to vertex $j$?

I imagine this might be difficult for generic graphs, so let's focus on the case where the graph is the complete graph, $K_n$. There are ${n\choose 2}^k$ edge sequences of length $k$. How many of these contain at least one subsequence which is a walk between two distinct vertices $i$ and $j$?

First two cases: If $k=1$, then there is only one sequence: the one consisting of the edge between the vertices, call it $(e)$. If $k=2$, the way I tried to do this is by systematically building all the sequences from smaller walks and filling the rest of the sequence with dummy edges. There are $n-2$ walks of length $2$ and no need for dummy edges. There's only walk of length 1, so we can have sequences $(e,\bar{e})$ and $(\bar{e},e)$ where $\bar{e}$ represents any of the ${n\choose 2}$ edges. We must be careful about double counting though, there aren't $2{n\choose 2}$ choices for inserting the dummy edge, but rather, $2{n\choose 2}-1$. Thus, we have there are $(n-2)+ 2{n\choose 2}-1$ sequences of length two that contain at least one subsequence which is a walk between two distinct vertices. The case for $k=3$ is way hairier: when building up sequences from walks of length 1 we get ${n\choose 2}^2+{n\choose 2}\left({n\choose 2}-1\right)+\left({n\choose 2}-1\right)^2$ but some of these are the same as the $(n-2)(3{n\choose 2} -2)$ we get when building up from walks of length 2.

I'd appreciate any references or if anyone has seen this quantity or something similar I'd love to know about it. Perhaps there's something else it can be mapped to that's easier to digest.

For context, this quantity came up while I was studying contact processes on networks. Thanks!

Answer 1

We can find a satisfying formula for this when the set of walks do not have any repeating edges (within or between them: a set of edge-disjoint paths). Suppose that we have some graph on 10 edges with vertices $i$ and $j$ that are endpoints of an edge $a$. They also have walks $bc$ and $def$ between them (I'm ignoring longer walks for simplicity).

First exercise: Let $c_k$ be the number of strings of length $k$ that do not have $bc$. The number of such strings of length $t$ that do not start with $b$ is $9c_{k-1}$. The number that do start with $b$ is $c_{k-1}-c_{k-2}$. So, we have $c_k=10c_{k-1}-c_{k-2}$. The initial conditions are $c_1=10$ and $c_2=99$.

Now, let $d_t$ be the number of strings of length $t$ that do not contain $a$, $bc$ or $def$. Then our recursive expression is $d_k=9d_{k-1}-d_{k-2}-d_{k-3}$, with $d_1=9,d_2=80,d_3=710$. (Why?)

Finally, if $f_k$ is the number of strings of length $k$ that have at least one of $a,bc,def$, then $f_k=10^k-d_k$.

The recursion for avoiding a string of length $t$ consisting of $t$ distinct characters is simply $d_k=nd_{k-1}-d_{k-t}$ (where $n$ is the total number of characters). If we forbid $s_1$ strings of length 1, $s_2$ strings of length $2$, etc, and all of those strings have disjoint sets of characters, then we get $d_k=nd_{k-1}-s_1d_{k-1}-s_2d_{k-2}-\ldots$

Once we allow repeating characters in the forbidden strings things get messier and you won't find a satisfying general formula.

If you'd like to explain your application to me (here or over email) I can perhaps help you find an approximation that will work.