I'm trying to investigate the property of the following quantity on a weighted graph $G=(V, E, W)$, where $V$ is the set of vertices, $E$ is the set of edges, and $W:V\to\mathbb{R}$ is some positive weight function :
$$C_{ij}(t)=\sum_{\Gamma\in C} \frac{t^{l(\Gamma)}}{l(\Gamma)!}\prod_{X\in\Gamma}W(X). $$
Here, $i$ and $j$ are indices of two distinct vertices, $C$ is a set of paths in $G$ which starts from $i$ and ends at $j$, $\Gamma$ is a element of $C$ and therefore a path, $l(\Gamma)$ is the total number of vertices in $\Gamma$ and $X$ denotes a vertex from $\Gamma$. The element of $C$ satisfies one of the following conditions:
- Paths are simple, i.e. no repeating vertices. Denote such set by $C_1$ for later reference.
- Paths are irreducible, i.e. apart from two consecutive vertices in a path, no other pairs of vertices in the path are adjacent to each other. Denote such set by $C_2$ for later reference.
Now consider a inter-connected 1D lattice chain. In this very special case both $C_1$ and $C_2$ has only one element--it's just the direct path connecting two points. Click for illustration. $J$ and $h$ around each vertex is the weight function.
However, once we generalize into higher dimensions, case changes drastically. Now consider a 2D grid. Not only are there infinitely many paths in both $C_1$ and $C_2$, certain elements belonging to $C_1$ may not belong to $C_2$. Click for an example.
What I'm interest of $C_{ij}(t)$ is when $i$ and $j$ separate from each other at a very long distance. Formally, let $r=d(i,j)$ denote the shortest distance(Euclidean, Manhattan, whatever is convenient) between $i$ and $j$. Does there exist a positive constant $c$ such that when $r$ is substituted for $ct$ in the definition of $C_{ij}(t)$ and $t$ tends to infinity, $C_{ij}(t)$ a bounded by an constant dependent only on $c$ and weight function $W$?
I believe one difficulty is that there's no easy way to enumerate all path from $i$ to $j$, also dealing with factorials is hard.
Any suggestions/ideas are welcome. Thanks!
Edit 2020/01/20: In fact, an lower and upper bound of $c$ can be derived. Let $c_j$ be the corresponding constant of $C_j$.
Denote the set of one shortest path by $C_0$, then $c_0$ is equal to its 1D counterpart, since two cases are essentially the same.
Denote the set of all walk(i.e. may have repeating edges or vertices) by $C_\infty$, and construct a matrix $\mathbf{H}$ whose element $$H_{ij}=\sqrt{W(i)W(j)},$$ where $i$ and $j$ are the indices of two vertices. Then we assert \begin{align} C_{ij}(t)&=\sqrt{W(i)W(j)}{[e^{\mathbf{H}t}]}_{ij}\\ &=\sqrt{W(i)W(j)}\sum_{l\ge0}\frac{t^l}{l!}{[\mathbf{H}^l]}_{ij}\\ &=\sqrt{W(i)W(j)}\sum_{l\ge0}\frac{t^l}{l!}H_{iX_1}H_{X_1X_2}\ldots H_{X_{l-1}j}\\ &=\sum_{l\ge0}\frac{t^l}{l!}\prod^{l}_{p=0}W(X_p), \end{align} with ${\{X_n\}}^l_{n=0}$ being a indices of vertices in a path connecting $i=X_0$ and $j=X_l$. Clearly in the last line the expression says the same thing as its definition. $c_\infty$ can be instantly derived through Fourier transform(see this paper for a hint) and found to be a constant. Note that $C_{ij}(t)$ clearly serves as a generating function of $t$.
Since $C_0\subset C_1 \subset C_2 \subset C_\infty$, we have $c_0\leq c_1\leq c_2\leq c_\infty$.