Measures of spread of information are introduced, with applications to neuronal activity in regions of a brain or to the design of artificial robotic networks in which efficient transmission of information is sought. We make links to spectral connectivity measures in graphs, such as spanning trees and higher-order diameters (as defined here). The exposition is then specialized to regular graphs by developing a formula that expresses the number of spanning trees in terms of walks in the complementary graph. Using traces, we then develop bounds for the number of spanning trees. Two approaches are used to establish such bounds: the first involves a logarithmic series expansion of the number of spanning trees in the complementary graph, while the second relies on certain \(l_p\) norm inequalities. Consequences to bipartite graphs are then examined.
The diameter of a directed graph (digraph) is a feature that is both of mathematical interest and of importance for applications in which the digraph models a network, directed edges represent unidirectional communication pathways within the network, and the diameter relates to how efficiently information can spread through the network; see [16, 17]. Applications to neuronal communication appear in [2] and [7]. It follows that the diameter is a measure of the connectivity of the graph or digraph; [16]. Another useful measure of graph connectivity is the number of spanning trees that the graph has, greater connectivity being associated with a larger number of spanning trees; see [8, 10, 6, 1]. We present a relation between these two concepts for graphs, for cases in which the adjacency matrix has few distinct eigenvalues. In practical applications, however, communication pathways may be imperfect, probabilistic, or weak. Such settings call for generalizations of the diameter to reflect the potential inadequacy of individual edges to ensure successful information transfer. In the first part of this work we introduce generalizations, which we call higher-order diameters, along with velocity of spread and probability of spread, motivated by abstract mathematical properties as well as applications in computer science and neuronal communication. These features lead to the question of how well the local activation of a small subset of vertices can induce a spread of activity throughout the entire graph (or digraph) in which communication occurs over directed links. Activation of new vertices often succeeds only if a vertex is the target of multiple, already-active, sources. In certain applications it may be advantageous for activation to spread quickly. We recommend [3] and [17] for descriptions of the bootstrap percolation and its application to the random regular graphs. Applications to trees appear in [9].
We start with a digraph \(G\) with vertex set \(V\). Each vertex may be in one of two states: active or inactive. An edge of \(G\) is an ordered pair \((i,j)\) of vertices; we call \(i\) the source vertex and \(j\) the target vertex. The edge \((i,j)\) is often viewed as an arrow emanating from vertex \(i\) and pointing to vertex \(j\). The set of edges of \(G\) is denoted by \(E\). A digraph is a graph if whenever \((i,j)\) is an edge \((j,i)\) is also an edge.
Let us formulate now the activation, or spreading, process in an arbitrary digraph \(G\). Partition the vertices \(V\) of \(G\) into a set \(S_0\) of active vertices and the complement \(S_0^c\) of \(S_0\) in \(V\) of inactive vertices. Fix a natural number \(t\) called the activation threshold. An inactive vertex \(v\) becomes active if it has \(t\) or more arrows with source vertices in \(S_0\) pointing to it. Upon performing this task we have a new set \(S_1\) of active vertices, and \(S_0\subseteq S_1\), as we insist that active vertices remain active.
The general step is as follows. We are in possession of set \(S_{i-1}\) of active vertices. Activate vertex \(v\) if it has \(t\) or more arrows with source vertices in \(S_{i-1}\) pointing to it. Upon performing this task we are in possession of a new set \(S_i\) of active vertices, and \(S_{i-1}\subseteq S_{i}\). We say that \(S_i\) is obtained from \(S_0\) after \(i\) \(\it steps\) of activation.
Evidently \(S_0\subseteq S_1\subseteq\cdots\subseteq S_i\subseteq \cdots .\) As we keep increasing \(i\), the following mutually exclusive cases will (obviously) always occur: either \(\exists m\) such that \(|S_m|<|V|=n\), and \(S_i=S_m\), for all \(i\geq m\). or \(\exists m\) such that \(|S_m|=|V|\). In the latter case we say that digraph \(G\) has been brought to synchrony, while in the former case we say that the activation process ended in a stationary state.
We say that vertex \(x\) of digraph \(G\) is activated from subset \(S\) if, starting from the vertices of \(S\) as the initially active vertices, \(x\) is activated after a finite number of steps.
For a given starting subset \(S\) with \(s\) vertices we denote by \(d(S,t)\) the smallest number of steps that brings the digraph to synchrony. When a digraph cannot be brought to synchrony from a set \(S\), for activation threshold \(t\), we write \(d(S,t)=\infty\). A maxmin argument of this quantity is very natural to consider. Define therefore \(d_{st}=max_{S:|S|=s}d(S,t).\) We call the integers \(d_{st}(G)\) the higher-order diameters of digraph \(G\). As is easy to see from the definitions, \(d_{11}\) is just the diameter of the digraph. A digraph is connected if there exists a path (of edges) starting at vertex \(i\) and ending at vertex \(j\), for all \(i,j\); \(i\neq j\). In terms we just defined, a digraph is connected if and only if it can be brought to synchrony by starting at any of its vertices and using an activation threshold of 1. This is, in particular, applicable to graphs as well. A subset with \(s\) vertices of digraph \(G\) is called a \(s-\)subset.
Fix a threshold \(t\) and a value of \(s\). Besides \(d_{st}\), we briefly mention a couple of other measures of spread on digraphs that can prove useful. As a first intuitive example, the ratio \(p_{st}(G)=\)(number of \(s-\)subsets \(S\) that bring \(G\) to synchrony)/(number of all \(s-\)subsets) signifies the probability of bringing digraph \(G\) to synchrony from a randomly chosen \(s-\)subset. Generally we are interested in identifying digraphs with large \(p_{st}\). It might also be observed that there are many instances when a digraph has a large \(p_{st}\) but the number of steps required to attain synchrony are generally quite large, which may be rather inadequate for quick activation. We could tune this up by defining another measure \(v_{st}(G)\), which we call the velocity to synchrony, as follows:
\[{n\choose s}v_{st}(G)=\sum\limits_{S:|S|=s}d(S,t)^{-1}.\]
Observe that when \(S\) does not induce synchrony, \(d(S,t)=\infty\), and we simply add a zero to the sum. Intuitively, the velocity \(v_{st}\) yields the average speed to the synchrony of \(G\) across all \(s-\)subsets. High values of \(v_{st}\) are typically desirable, since synchrony is then speedily achieved.
The numbers \(p_{st}\) have been defined in the literature and are associated to bootstrap percolation. Previous literature in this area has focused on critical transitions, or abrupt changes in the probability of synchrony as the connection probability within a graph is increased. In particular, the role of digraph spectra is studied at some length in [4] and [18]. On the other hand, we have not encountered the concept of velocity to synchrony used in the digraph (or network) optimization literature so far.
Our aim in this paper is to focus entirely on the graph diameter \(d_{11}\) and, further still, recast this study in terms of the number of spanning trees of the graph. We make the simplifying assumption that the underlying graph that connects the neurons is regular. Since we want a quick spread to activate the whole graph two things seem intuitive:
(a) Among all graphs with \(n\) vertices and \(m\) edges we want those that are in some sense most connected. This allows synchrony to occur quickly. We want to reach from anywhere to anywhere else in a minimum number of steps.
(b) Avoid having short cycles, like triangles or squares. Evidently they impede quick global spread, since ”we tend to move in circles”.
Part (a) may be interpreted in several ways. Among them is that such graphs have a maximal number of spanning trees. This produces, through Kirchhoff’s matrix-tree theorem, a connection to spectra of Laplacian matrices. This is the connection that we explore in this paper in the sections that follow. Both parts (a) and (b) also intimate that graphs with a small diameter might be good candidates. The diameter involves choices of paths or walks in the graph. Preferably we should reach from anywhere to anywhere else in just a few steps. At least for \(t=1\) this makes sense. At a minimum, an interplay between the number of spanning trees and walks seems to clearly emerge. We shall explore this connection in the rest of the paper as well. For graphs, but not digraphs, we also observe that the diameter \(d_{11}\) is known to be bounded above by the number of distinct eigenvalues of the Laplacian. Graphs with few distinct eigenvalues and a large number of spanning trees are therefore of great interest; see [18] for some constructions of such graphs. These heuristics are supported, in part, by the results found in [7] mentioned at the end of this section.
Let us introduce the necessary vocabulary on graph complexity. The graphs that arise are labeled, finite, loopless, undirected, and without multiple edges. Standard terminology is used and we assume that the reader is familiar with such notions as degree of a vertex, path, graph connectivity, tree and spanning tree, adjacency matrix and the Laplacian; see [, 12]. By the order of a graph we understand the number of its vertices, and by size the number of its edges. A graph is called \(regular\) if the degrees of its vertices are equal. For clarity we also remind that a \(walk\) of length \(k\) (or \(k-\)walk) is a sequence of vertices and edges \(v_1e_1v_2e_2\cdots v_ke_kv_{k+1}\), where \(e_j\) is the edge joining vertices \(v_j\) and \(v_{j+1}.\) The beginning of the walk is vertex \(v_1\) and the end of the walk is vertex \(v_{k+1}\). Vertices and edges may be repeated in this sequence. The walk is closed if \(v_1=v_{k+1}.\) A m-cycle is a sequence of vertices and edges \(v_1e_1v_2e_2\cdots v_me_mv_{m+1},\) where all vertices \(v_i\) are distinct except for \(v_1\) and \(v_{m+1}\) which are the same; \(m\geq 2.\)
To simplify notation we often prefer to denote the vertices of a graph of order \(n\) by the symbols \(1, 2, \ldots , n\). We say that vertices \(i, j, k\) form a \(triangle\) in graph \(G\) if \(\{i,j\}\), \(\{j,k\}\), \(\{k,i\}\) are edges of \(G\). When counting, it is important to realize that a triangle actually corresponds to six closed 3-walks, since a walk is a sequence, and we can start the walk at each one of the three vertices and walk around from each starting vertex either clockwise or counterclockwise.
Denote by \(D\) the diagonal matrix with the degrees of the vertices of graph \(G\) as entries (written always in the same fixed order), by \(A\) the adjacency matrix and by \(L=D-A\) the Laplacian. The complexity of graph \(G\) is the number of spanning trees of \(G;\) we denote it by \(t(G).\) The log-complexity of \(G\) is defined as \(ln(t(G)).\) We remind the reader of a few well-known results, see [4, 5] and [8], that we rely on and use freely in this article:
1. The \((i,j)^{th}\) entry of \(A^r\) is equal to the number of walks with \(r\) edges staring at vertex \(v_i\) and ending at vertex \(v_j\). In particular, the number of closed \(r-\)walks at vertex \(v_i\) is the \((i,i)^{th}\) entry of \(A^r.\) Consequently \(tr(A^r)\), the trace of \(A^r\), is equal to \(w_r(G)\), the total number of closed \(r-\)walks in graph \(G\).
2. If \(\lambda_1\leq\lambda_ 2\leq\ldots\leq\lambda_n\) are the eigenvalues of the \(n\times n\) adjacency matrix \(A,\) then \(tr(A^r)=\sum\limits_{i=1}^n\lambda_i^r.\)
3. If the graph is regular of degree \(d,\) then \(L=dI-A,\) with \(I\) denoting the identity matrix. Furthermore, the eigenvalues \(\mu_i\) of \(L\) may be written in this case as \(\mu_i=d-\lambda_i,\) \(1\leq i\leq n.\) Since the row sums of \(L\) are always 0, we have \(\mu_n=0.\)
4. It is an easy consequence of Kirchhoff’s theorem that the complexity of graph \(G\) is equal to \(\frac 1n\mu_1\mu_2\cdots\mu_{n-1}\) where \(n\) is the \(order\) of \(G\) and \(\mu_1\geq\mu_2\geq\ldots\geq\mu_{n-1}\geq\mu_n(=0)\) are the eigenvalues of the Laplacian \(L\) of \(G.\)
The complement \(G^c\) of graph \(G\) is the graph with same set of vertices as \(G\) in which \(e\) is an edge if and only if \(e\) is not an edge in \(G.\) We denote by \(A^c\) and \(L^c\) the adjacency matrix and the Laplacian of \(G^c\). Let \(I\) be the identity matrix and \(J\) be the square matrix with all entries equal to 1. Evidently \(A+A^c=J-I\) and \(L+L^c=nI-J.\) These equalities allow us to immediately conclude as follows:
5. The eigenvalues of \(L^c\) are \(\bar{ \mu}_i=n-\mu_i,\) \(1\leq i\leq n-1\) and \(\bar{\mu}_n=0.\) In view of 4. we have \(t(G^c)=\frac 1n\prod_{i=1}^{n-1}\bar{\mu}_i=n^{n-2}\prod_{i=1}^ {n-1}(1-\frac {\mu_i}n).\) This equation is true for any graph, regular or not.
6. Assume now that \(G\) is a regular graph of order \(n\) and degree \(d.\) We have \(L=dI-A\) and, more generally, \(L^r=(dI-A)^r=\sum\limits_{i=0}^r(-1)^i{r\choose i}d^{r-i}A^i.\) In general, for any square matrix \(B,\) we write \(B^0=I.\) It follows that \(tr(L^r)=\sum\limits_{i=0}^r(-1)^i{r\choose i}d^{r-i}tr(A^i).\)
Some connections linking the number of distinct eigenvalues of the Laplacian, the diameter, and the complexity of a graph are known. We refer now to some of these. For instance, it is known, and not hard to prove, that the diameter of any graph (but not digraph) is strictly less than the number of distinct eigenvalues of the Laplacian; see [4]. Denote by \(g(n,d)\) the set of graphs with \(n\) vertices, regular of degree \(d\). The following is proven in [7, Theorem 4]. If a graph \(G^*\) with two distinct non-zero eigenvalues of the Laplacian and a minimum number of triangles exists in \(g(n,d)\), then \(G^*\) has maximal complexity over \(g(n,d)\). Such a graph \(G^*\) has diameter at most 2, necessarily. Infinite families of such graphs exist. Additional noteworthy examples are the strongly regular triangle-free graphs, such as the Hoffman-Singleton and the Higman-Sims graphs. The case we make is that, in certain settings, and probably quite often, graphs of smallest diameter and graphs of maximal complexity coincide. Minimizing \(d_{11}(G)\) and maximizing \(t(G)\) are closely related problems in general, and in certain settings lead to the same solution, as seen in the examples mentioned.
Section 2 offers an exact formula for the number of spanning trees in regular graphs in terms of a series expansion using just the number of closed walks in the complementary graph. Relying on this expansion, and using certain \(l_p\) inequalities, Section 4 provides both upper and lower bounds for the number of spanning trees in regular graphs. The last section examines these results and bounds in the special case of bipartite graphs.
Spanning trees of a graph are typically numerous and diverse. By contrast, walks in a graph are just about the easiest to construct and grasp. Our next result expresses the log-complexity of a regular graph as an infinite alternating series that involves closed walks. Closed walks are traces of the adjacency matrix, and while they are particularly intuitive and easy to use, there are other meaningful symmetric functions of eigenvalues that can be used instead; see [13].
Proposition 2.1. For any graph G of order \(n\), with connected complement \(G^c\) and Laplacian L, we have \(ln(t(G^c))=(n-2)ln(n)-\sum\limits_{r\geq 1}{{tr(L^r)}\over {rn^r}}\). The error in this series expansion is bounded as follows:
\[\left|ln(t(G^c))-\left[(n-2)ln(n)-\sum\limits_{r=1}^m{{tr(L^r)}\over {rn^r}}\right]\right|\leq{{ tr(L^{m+1})}\over {(m+1)n^m(n-\rho )}}\leq{{n-1}\over {m+1}}\cdot{{ \rho}\over {n-\rho}}\cdot ({{\rho}\over n})^m,\] where \(\rho\) is the spectral radius of L.
Proof. We start with the formula for \(t(G^c)\) in 5. above, and rest upon routine series expansions of the logarithm. \[\begin{aligned} \label{eq1} ln(t(G^c)) &= (n-2)\ln(n) + \sum\limits_{i=1}^n \ln\left(1 – \frac{\mu_i}{n}\right) \notag\\ &= (n-2)\ln(n) – \sum\limits_{i=1}^n \left( \sum\limits_{r=1}^{\infty} \frac{1}{r} \left(\frac{\mu_i}{n}\right)^r \right) \notag\\ &= (n-2)\ln(n) – \left( \sum\limits_{r=1}^{\infty} \frac{\text{tr}(L^r)}{rn^r} \right). \end{aligned} \tag{1}\]
Observe that connectivity of \(G^c\) implies \(0\leq\frac {\mu_i}n<1,\) for all \(i\), and in particular it implies that \(\rho=\mu_1\) is strictly less than \(n\). The series in (1) therefore converges, and in fact converges absolutely. This allows us to interchange the order of summation. The formula for the error is the integral version (best in this case) associated to the Taylor polynomials that arise. ◻
When the graph is regular the relationship between \(A\) and \(L\) is particularly simple. This allows us to link the complexity of \(G^c\) to the number of closed walks in \(G\) by way of the traces that arise.
Theorem 2.2. If \(G\) is a regular graph of order \(n\) and degree \(d\), with \(d<n/2\), then the log-complexity of \(G^c\) is expressed in terms of \(w_k(G )\), the number of closed walks with \(k\) edges in \(G\), as follows: \[ln(t(G^c))=ln(n^{-2}(n-d)^n)+\sum\limits_{k=2}^{\infty} (-1)^{k-1}\frac {w_k(G)}{k(n-d)^k}.\]
Proof. Observe first that the condition \(d<n/2\) forces \(G^c\) to be connected; this is true since the smallest eigenvalue of \(A\) cannot be less than \(-d\) and hence the spectral radius of \(L\), by 5., is strictly less than \(n\). Start with the expression for \(ln(t(G^c))\) given in Proposition 2.1. Focus on this series, use the content of 6. and change the order of summation, which can be done because of absolute convergence. This yields
\[\begin{aligned} \sum\limits_{r=1}^{\infty}\frac {tr(L^r)}{rn^r}=&\sum\limits_{r=1}^{\infty}\frac1{rn^r}\left(\sum\limits_{k=0}^r(-1)^k{r\choose k}d^{r-k}tr(A^k)\right)\notag\\ =&\left(\sum\limits_{r=1}^{\infty}\frac 1{rn^r}d^r\right)tr(A^0)+\sum\limits_{k=1}^{\infty}\left(\sum\limits_{r=k}^{\infty}\frac 1{rn^r}{r\choose k} d^{r-k}\right)(-1)^ktr(A^k)\notag\\ =&-ln\left(1-\frac dn\right)tr(A^0)+\sum\limits_{k=1}^{\infty}\frac {(-1)^k}{k(n-d)^k}tr(A^k). \end{aligned}\]
The last sign of equality is explained by making use of the identity \[\sum\limits_{r=k}^{\infty}\frac 1{rn^r}{r\choose k}d^{r-k}=\frac 1{n^k}\left(\sum\limits_{s=0}^{\infty}\frac {{{k+s}\choose s}}{k+s}\left(\frac dn\right)^s\right)=n^{ -k}k^{-1}\left(1-\frac dn\right)^{-k}=\frac 1{k(n-d)^k}.\]
Substituting this information into the expression for \(ln(t(G^c))\) found above, and using 1. to introduce the closed walks for the traces that arise, we finally obtain \(ln(t(G^c))=(n-2)ln(n)-\left(\sum\limits_{r=1}^{\infty}\frac {tr(L^r)}{r n^r}\right)=(n-2)\cdot ln(n)+n\cdot ln(1-\frac dn)\) \(+\sum\limits_{k=1}^{\infty}\frac {(-1)^{k-1}tr(A^k)}{k(n-d)^k}=ln(n^{-2} (n-d)^n)+\sum\limits_{k=2}^{\infty}(-1)^{k-1}\frac {w_k(G)}{k(n-d)^k}.\) Since \(d\) is the largest eigenvalue of \(A\) in absolute value, the last series converges when \(d<n-d\), which restricts \(d<n/2\), as enunciated. This is the expression we sought. ◻
It may be helpful to make some observations regarding the speed of convergence of the walks formula given in Theorem 3.1.
A. If \(G\) is a graph of order \(n\) and degree \(d\), with \(d<n/2\), then \(t(G^c)\) is equal to the closest integer to \[n^{-2}(n-d)^nexp\left(\sum\limits_{k=2}^b\frac {(-1)^{k-1}w_k}{k (n-d)^k}\right).\]
Here \(b\) is the smallest natural number with the property that \[n^{-2}(n-d)^n\cdot \left|exp\left(\sum\limits_{k=2}^m\frac {(-1)^{k-1} w_k}{k(n-d)^k}\right)-exp\left(\sum\limits_{k=2}^b\frac {(-1)^{k-1}w_k}{k(n-d)^k}\right)\right| <\frac 12,\] for all \(m>b.\)
The content of A. may be explained as follows. The “walks” series that appears in Theorem 3.1 is convergent; it is not always alternating, since some of its terms can be zero (this is the case in bipartite graphs, for instance). If we express the series as \(\sum\limits_ia_i\) then evidently \(a_i\rightarrow 0\) as \(i\rightarrow\infty .\) But the complexity \(t(G^c)=exp(\sum\limits_ia_i)\) is an integer. This tells us that we can identify \(t(G^c)\) by only using the first finite number of terms in the series. Indeed, since the sequence is convergent it is also Cauchy and we can stop summing when we reach consistent diminishing returns of less than \(\frac 12\) in the finite product \(\prod_{i=1}^mexp(a_i)\), which now unambiguously identifies \(t(G^c).\) An exact formulation of this argument is enunciated in A.
B. When in the presence of a regular graph \(H\) of degree \(r\) with \(n\) vertices it is helpful to always be aware of the bounds \(L(n,r)\leq t(H)\leq U(n,r)\). Here a lower bound \(L(n,r)\), initially due to McKay [14], takes the value \(L(n,r)=n^{-1}(2r)^kz^{n-1-k}\), with \(k\) being the integral part of \(\frac {n-2}2\) and \(z=\frac {nr-2rk}{n-1-k}\). Using probabilistic arguments McKay showed that this lower bound is almost always achieved by a regular graph with \(n\) vertices regular of degree \(r\) (sometimes called a “dumbbell graph”). Alon [1] also gives asymptotic lower bounds for the number of spanning trees in a regular graph. There are many choices for the upper bound \(U(n,r)\); see [8] for a list of such bounds. None known to the authors are always sharp, but we may use \(U(n,r)=n^{n-2}(\frac r{n-1})^{n-1}\), for instance. The integers in the interval \([L(n,r),U(n,r)]\) are the only ones that can possibly occur as values for \(t(G^c)\) and Theorem 3.1 pinpoints the exact integral value through the converging process described.
C. In potential applications of Theorem 3.1 accurate estimation of the natural number \(b\), introduced as the bound of summation in A., may become important. We believe that this is possible to accomplish by a more careful study of the closed walks \(w_k(G)\), at least for specialized classes of graphs \(G.\) The last section examines the case of bipartite graphs, for instance, in which case bound \(b\) (due to monotonicity) is easier to address. We shall not deal with the full generality of this issue in this paper.
There are many upper bounds on graph complexity, mostly based on variants of the geometric-arithmetic mean inequality and the log-concavity of the determinant of a positive definite matrix; see [14, 8, 10, 6, 1]. Explicit lower bounds are rare and typically more difficult to obtain, especially when features of the graph such as cycles or paths need to be highlighted. It is helpful, however, to be aware of the asymptotic lower bounds for regular graphs established in [14] and [1]. The lower bounds we present in this paper are explicit and shown to be asymptotically exact. We start developing lower bounds based on the results presented in Section 3.1 and some basic \(l_p\) inequalities.
For \(p\) a natural number and \(x\) a vector, we write \(|x|_p=(\sum\limits_i|x_i|^p)^{1/p}\) for the \(l_p\) norm of \(x.\) From inequalities on \(l_p\) norms it is known and easy to check that \(|x|_k\leq |x|_m,\) for \(1\leq m\leq k.\) If \(x\) is the vector of eigenvalues of the Laplacian \(L\) of a graph \(G\), then it is clear that \(|x|_k=(tr(L^k))^{1/k}.\) If graph \(G\) is of order \(n\) and degree \(d\) then we may also readily calculate that \(trL=nd,\) \(tr(L^2)=n(d^2+d)\) and \(tr(L^3)=nd^3+3nd^2-6\Delta\), where \(\Delta\) stands for the number of triangles in \(G\). We freely use these expressions in the remainder of this section.
To simplify notation write \(L_m=(tr(L^m))^{1/m}\), which is the \(l_m\) norm of the spectrum of the Laplacian \(L\).
Theorem 3.1. If \(G\) is a regular graph of order \(n\) with its Laplacian \(L\) satisfying the inequality \(L_m<n\) for some integer \(m\geq 2\), then the complexity of the complement \(G^c\) verifies the inequality \[t(G^c)\geq n^{n-2}\left(1-{{L_m}\over n}\right)exp\left(-\sum\limits_{k=1}^{ m-1}{{[tr(L^k)-L_m^k]}\over {kn^k}}\right).\]
The inequality becomes equality as \(m\rightarrow\infty .\)
Proof. Using the \(l_p\) inequalities, for \(2\leq m\leq k\) we may generally write \(ln(t(G^c))=(n-2)ln(n)-\sum\limits_{k\geq 1}{{tr(L^k)}\over {kn^k}}\geq (n-2)ln(n)-\sum\limits_{k=1}^{m-1}{{tr(L^k)}\over {kn^k}}-\sum\limits_{k\geq m}{{ L_m^k}\over {kn^k}}.\) Adjusting summations to fit in the term \(ln(1-{{L_m}\over n}),\) the inequality may be expressed in the form \[\label{eq2} ln(t(G^c))\geq (n-2)ln(n)+\sum\limits_{k=1}^{m-1}{{[L_m^k-tr(L^k)]}\over {kn^k}}+ln\left(1-{{L_m}\over n}\right) \tag{2}\]
The stated condition \(L_m<n\) assures the convergence of \(ln(1-{{L_m}\over n})\) in (2). It also immediately follows from (2) that, as \(m\rightarrow\infty\), we simply recapture the incipient content of Proposition 2.1. ◻
The weakest case occurs when \(m\) is the smallest, that is \(m=2\). In this case Theorem 4.1 yields the formula \[t(G^c)\geq n^{n-2}\cdot \left(1-\frac {L_2}{n}\right)\cdot exp\left(\frac {L_2}{n} -d\right),\] where \(d\) is the degree of \(G\), and with the convergence requirement \(d(d+1)<n.\) As mentioned, here \(L_2=(tr(L^2))^{1/2}=\sqrt {n(d^2+d)}\).
If \(\overline {d}\) is the degree of \(G^c\) we have \(d+\overline {d}=n-1.\) This allows us to express the above inequality without reference to the complementary graph \(G^c\).
Corollary 3.2. If \(G\) is a graph of order \(n\) regular of degree \(d\) satisfying the restriction \((n-1-d)(n-d)<n,\) then \(G\) has at least \(n^{n-2}\cdot \left(1-\sqrt {\frac {(n-1-d)(n-d)}n}\right)\cdot exp\Big(-(n-1-d) +\sqrt {\frac {(n-1-d)(n-d)}n}\Big)\) spanning trees.
Since the case \(m=2\) yields the weakest inequalities, it is not surprising that the degree restriction in Corollary 3.2 is rather severe. It basically requires that the degree \(d\) of the graph \(G\) be within about a square root of \(n\) of the degree of the complete graph of order \(n,\) that is, \(d\geq n-\sqrt {n}.\) In accordance with Theorem 3, however, we know that by increasing \(m\) the resulting inequalities become asymptotically arbitrarily sharp. This restriction can be controlled in large measure by expanding the series in powers of \(L_m\) rather than simply \(L_2\). Doing so will bring into focus features of the graph other than its degree, such as cycles of higher order.
To that end, we now study in further detail the case \(m=3\) of Theorem 4.1, since it provides a lower bound on complexity in terms of both the degree as well as the number of triangles in the graph. We saw that \(tr(L^3)=nd^3+3nd^2-6\Delta\), with \(\Delta\) signifying the number of trangles in the graph \(G\). Moreover, simple counting shows that if \(d\) (respectively \(\overline {d}\)) and \(\Delta\) (respectively \(\overline{\Delta}\)) denote the degree and the number of triangles in \(G\) (respectively \(G^c\)), then we have \(d+\overline {d}=n-1\) and \(\Delta +\overline {\Delta }={n\choose 3}-\frac { nd\overline {d}}2\); see also [15]. Specializing Theorem 4.1 to the case \(m=3\) we deduce that \[\label{eq3} t(G^c)\geq n^{n-2}\cdot \left(1-\frac {L_3}{n}\right)\cdot exp\left(\frac {L_3}{n}-d+\frac {L_3^2}{2n^2}-\frac {d(d+1)}{2n}\right) \tag{3}\]
Since we are concerned with the graph \(G^c\), specifically \(t(G^c),\) it is helpful to express \(d\) and \(L_3\) solely in terms of features of \(G^c\) such as \(\overline {d}\) and \(\overline {\Delta }.\) We have \(L_3^3=tr(L^3)=n(n-1-\overline {d})^2(n+2-\overline {d})-6({n\choose 3}-\frac { n\overline {d}(n-1-\overline {d})}2-\overline{\Delta }).\) In summary, omitting reference to the graph complement, we obtain
Corollary 3.3. If \(G\) is a graph of order \(n\) regular of degree \(d\) and having \(\Delta\) triangles, then \[t(G)\geq n^{n-2}\cdot \left(1-\frac{L_3}{n}\right)\cdot exp\left(\frac {L_3}{n}-(n-1-d)+\frac { L_3^2}{2n^2}-\frac {(n-d)(n-d-1)}{2n}\right),\] where \(L_3\) is defined by \(L_3^3=n(n-1-d)^2(n+2-d)-6\left({n\choose 3}-\frac {nd(n-1-d)}2-\Delta \right).\) The inequality holds true whenever \(0\leq L_3<n\).
Example 3.4. Consider the graph \(H\) with 10 vertices, labeled 0,1,…,9 regular of degree 3. Graph \(H\) has edges 12, 13, 23, 14, 26, 35, 45, 56, 47, 68, 79, 70, 89, 80, 90. We observe that \(H\) has 3 triangles. To start with, a direct calculation shows that \(G=\overline H\) has 2080524 spanning trees. Our interest is in examining the lower bound on the complexity of the graph \(G=\overline {H}\) as highlighted in Corollary 3.3. By setting \(L_H\) as the Laplacian of \(H\) we verify that \(\frac {L_3}{n}=\frac {(tr(L_H^3))^{1/3}}n=\frac {\sqrt[3]{522}}{10}=0.8051748 <1,\) which allows the application of Corollary 3.3. On the log scale we obtain a lower bound of 14.31436 and may therefore write \(14.54813=ln(t(G))>14.31436.\) Foregoing the log scale, the value of the lower bound turns out to be 1646819 which is indeed less than the true complexity of 2080524. Theorem 3 informs us that, by increasing \(m\), the lower bounds get arbitrarily close to \(t(G)\). We point out that a lower bound for \(t(G)\) cannot be obtained by using just the degree (that is, \(m=2\)), as in Corollary 3.2, since in this example \(3\cdot 4=d(d+1)<n=10\) does not hold true.
The structure of graphs with an extreme number of triangles is relatively well-known; see [11] and [12]. Corollary 3.3 shows how the number of triangles in a graph affects its number of spanning trees.
As is widely known, a bipartite graph has no closed walks of odd length, and is characterized by this property; see [5]. We use the results in the previous two sections to investigate the complexity of graphs that are complements of bipartite graphs. Let \(G\) be a bipartite graph of order \(n,\) regular of degree \(d.\) We remind that \(w_k(G)\) denotes the number of closed \(k-\)walks in \(G.\) When the presence of \(G\) is understood we simply write \(w_k\) for \(w_k(G).\) As mentioned, the bipartite assumption on \(G\) forces \(w_k(G)=0\) for all odd \(k\geq 1.\)
Theorem 4.1. If \(G\) is a bipartite graph of order \(n\) regular of degree \(d\), and \(m,\) \(k\) are positive integers, then \(a(n,d,m)\leq t(G^c)\leq b(n,d,k),\) where \[a(n,d,m)=(n-d)^n\cdot n^{-2}\cdot\sqrt {1-y^2}\cdot exp\left(-\sum\limits_{1 \leq s<m}\frac {(w_{2s}-(w_{2m})^{s/m})}{2s(n-d)^{2s}}\right),\] \[b(n,d,k)=(n-d)^n\cdot n^{-2}\cdot exp\left(-\sum\limits_{s=1}^k\frac {w_{2s}}{ 2s(n-d)^{2s}}\right)\] and \(y=\frac {(w_{2m})^{1/2m}}{n-d}.\) The lower bound holds true whenever \(y<1.\) When \(m\rightarrow\infty\), or when \(k\rightarrow \infty\), the respective inequalities become equalities.
Proof. For such \(G\) Proposition 2.1 takes the form \[ln(t(G^c))=ln(n^{-2}(n-d)^n)-\sum\limits_{s=1}^{\infty}\frac { w_{2s}(G)}{2s(n-d)^{2s}}.\]
From this, the choice of \(b(n,d,k)\) immediately follows. We now explain how the lower bound \(a(n,d,m)\) is achieved. Relying on 1. and 2. in Section 1, \(w_{2s}:=w_{2s}(G)=tr(A^{2s}),\) where \(A\) is the adjacency matrix of \(G\). The eigenvalues of \(A^2\) are nonnegative since they are the squares of the (real) eigenvalues of \(A.\) Making use of the \(l_p\) inequalities we may write \(tr(A^{2s})\leq (tr(A^{2m}))^{2s/2m},\) for \(s\geq m\geq 1.\) With \(y=\frac {tr(A^{2m})^{1/2m}}{n-d}=\frac {(w_{2m})^{1/2m}}{n-d},\) this yields
\[\begin{aligned} \sum\limits_{s=1}^{\infty}\frac {w_{2s}}{2s(n-d)^{2s}}\leq&\sum\limits_{1\leq s<m}\frac {tr(A^{2s})}{2s(n-d)^{2s}}+\sum\limits_{s\geq m}\frac {(tr(A^{2 m}))^{2s/2m}}{2s(n-d)^{2s}}\\ =&\sum\limits_{1\leq s<m}\frac {w_{2s}}{2s(n-d)^{2s}}+\sum\limits_{s\geq m}\frac {y^{2s}}{2s}\\ =&\sum\limits_{1\leq s<m}\frac {w_{2s}}{2s(n-d)^{2s}}-\frac 12[ln(1-y)+ln(1+y)]-\sum\limits_{1\leq s<m}\frac {y^{2s}}{2s}. \end{aligned}\]
Exponentiating both sides of the inequality yields \[t(G^c)\geq (n-d)^n\cdot n^{-2}\cdot\sqrt {1-y^2}\cdot exp \left(-\sum\limits_{1\leq s<m}\frac {(w_{2s}-(w_{2m})^{s/m})}{2s(n-d)^{2s}}\right)= a(n,d,m),\] as enunciated. From the formula for \(t(G^c)\) written in Proposition 2.1 it follows that when \(m\rightarrow\infty\), or when \(k\rightarrow\infty\), the respective inequalities become equalities. ◻
We illustrate the content of Theorem 4.1 by an example.
Example 4.2. Consider the bipartite graph \(G\) on vertices 0,1,…,9 regular of degree 3 with parts 1,2,3,4,5 and 6,7,8,9,0. Edges of \(G\) are 17 18 19 28 29 20 36 39 30 40 46 47 56 57 58. Direct computation shows \(t(G^c)=2034010.\) For graph \(G\) we have \(w_2=30,\) \(w_4=190,\) \(w_6=1530,\) … We examine the bounds for values \((m,k)\in \{(2,2),\) (3,3), (4,4), \((5,5)\), \((6,6)\}\) The corresponding values for \((a(n,d,m),b(n,d,k))\) are as follows: (2029504, 2039113), (2033738, 2034698), (2033985, 2034111), (2034007, 2034025), (2034010, 2034012). We observe that for \(m=6\) the lower bound yields the \(exact\) answer. It turns out that at \(k=7\) the upper bound also equals the exact answer.
The authors are grateful to the Referee for a very careful reading and for the many helpful suggestions that improved the clarity and presentation of the results.
This work was supported by grant number 2424684 from the National Science Foundation of the United States.