\input{stuff}


\title{\vspace{-0.8cm} Automated  Counting of Spanning Trees for  Several Infinite families of Graphs}
%setcounter{secnumdepth}{0} % DISABLES SECTION NUMBERING
\author{Pablo Blanco \and Doron Zeilberger}
 \date{}

\begin{document}

\usetikzlibrary{decorations.pathreplacing}
\usetikzlibrary{positioning,patterns}
\usetikzlibrary{arrows,shapes,positioning}
\usetikzlibrary{decorations.markings}


\maketitle

\vspace{-0.5cm}
\begin{abstract}
    Using the theoretical basis developed by Yao and Zeilberger, we consider certain graph families whose structure results in a rational generating function for sequences related to spanning tree enumeration. 
Said families are Powers of Cycles and Powers of Path; later, we briefly discuss Torus graphs and Grid graphs.
 In each case we know, a priori, that the 
set of spanning trees of the family of graphs can be described in terms of a finite-state-machine, and hence
there is a finite transfer-matrix that guarantees the generating function is rational. Finding this ``grammar'', and hence the transfer-matrix is very tedious, so a much more efficient
approach is to use experimental mathematics. Since computing numerical determinants is so fast, one can use the matrix tree theorem to generate sufficiently many terms, then fit the data to a rational function. The whole procedure can be done rigorously \textit{a posteriori}.

We also construct generating functions for the quantity ``total number of leaves'' over all spanning trees, and automatically derive the asymptotics for both number of spanning trees and
the sum of the number of leaves, enabling our computer to get the asymptotic for the average number of leaves per vertex in a random spanning tree in each family that always tends
to a certain number, which we compute explicitly. This number, that we christen the B-Z constant for the infinite family is always some (often complicated) algebraic number, in contrast
to the family of complete graphs where this constant is $1/e$ (a transcendental number).
    \end{abstract}

%
\section{Introduction and Background}
A subgraph $T$ of a graph $G$ such that $T$ is a tree with $V(T)=V(G)$ is called a \textit{spanning tree} of $G$. If $G$ is connected, simple, and not a tree, then it contain several spanning trees. When we count the number of spanning trees of a graph in this paper, we consider two isomorphic trees with different vertex labels to be different trees; for example, the complete graph on three vertices $K_3$ has three spanning trees, not one. For a connected graph $G$, we denote its number of spanning trees of $G$ by $\tau(G)$. Cayley's formula counts the number of spanning trees of a complete graph on $n$ vertices to be $n^{n-2} = \tau(K_n)$.

The \textit{generating function} $f(x)$ for a sequence $(a_0,a_1,\ldots)$ is the formal power series obtained by setting the sequence terms as its coefficients:
$$f(x):=\sum_{n=0}^\infty a_nx^n.$$
Whenever a sequence has a recurrence of finite length, with constant coefficients, it is called \textit{C-finite}. In other words, $(a_0,a_1,\ldots)$ is C-finite (of order $r$) if there is a fixed $r$ and coefficients $c_0,\ldots,c_{r-1}$ with $c_0\neq0$ such that
$$a_{n+r}=c_{r-1}a_{n+r-1} + \ldots +c_0a_n $$
for all $n\ge 0$.

The following is a useful property of C-finite sequences:
\begin{thm}
    \emph{\cite{concrete}[Kauers-Paule, Thm. 4.3]} A sequence $(a_0,a_1,\ldots)$ is C-finite (of order $r$) with recurrence
    $$a_{n+r}=c_{r-1}a_{n+r-1} + \ldots +c_0a_n $$
    if and only if
    $$\sum a_nx^n = \frac{p(x)}{1-c_{r-1}x+\ldots-c_1x^{r-1}-c_0x^r}$$
    for some polynomial $p(x)$ of degree at most $r-1$. 
\end{thm}
 In fact, the polynomial $p(x)$ in the previous Theorem is determined by the initial values $(a_0,\ldots,a_{r-1})$ of the sequence. Later, we state the starting index of (the underlying graph in) our sequence to disambiguate $p(x)$ in the sequence's rational generating function. 

 Due to the recursive nature of the graph families we consider, we presume that there is a finite Transfer Matrix which describes the corresponding sequence (see \cite{gordianknot} for more details). Thanks to this, we can find the sequence's rational generating function by computing a large number of terms in the sequence. The guessing is done in a Maple procedure, described in the same paper \cite{gordianknot}, called \texttt{GuessRec}.

 To generate the terms of whichever sequence we consider, we apply Kirchhoff's Matrix Tree Theorem, which allows us to compute the number of spanning trees of a(n $n$-vertex) graph by looking at its Laplacian matrix, taking an $n-1$ by $n-1$ (matrix) minor, and computing its determinant. Below, we define the Laplacian matrix of a graph for the reader's convenience.

 If $G$ is a (simple) graph with vertices $v_1,\ldots,v_n$, its \emph{Laplacian matrix} is a symmetric matrix with its entries defined by
 \begin{equation*}
     a_{i,j}:=\begin{cases}
         -1 & \text{if } v_i\sim v_j \text{ and } i\neq j\\
    \deg(v_i) & \text{if } i=j \\
     \end{cases}.
 \end{equation*}
Afterwards, we describe similar methods that we used to count the total number of leaves (across all spanning trees) for members in the same families (in \Cref{sec:CountingLeaves}). In addition, we consider an asymptotic constant relating total leaves to total spanning trees in any families (for which the constant is well-defined) in \Cref{sec:bz-constant}. We state our main experimental results in \Cref{sec:cycles} and \Cref{sec:paths}, then briefly consider an additional pair of graph families in \Cref{sec:gridtorus}. In \Cref{sec:verification} and \Cref{maple-package}, we include experimental verification of our results' correctness and then a description of the accompanying Maple package that we used. Additional outputs and code are available at \cite{spt}. Finally, we conclude with some conjectures in \Cref{sec:conj}



\section{Preliminaries} \label{graph-fams}
For ease of notation, we assume all graphs are simple. We write $[n]:=\{1,\ldots,n\}$.

\textbf{Definition.} For a graph $G$, the \textit{distance} $|u,v|$ between two vertices $u,v$ is the length of the shortest path between them. If $u$ and $v$ are in different components of $G$, we say the distance between them is infinite and write $|u,v|=\infty$.

\textbf{Definition.} Let $G$ be a graph. For an integer $k\ge1$, the $k$-th \textit{power} of $G$, denoted $G^k$, is the graph obtained from $G$ such that $V(G^k):=V(G)$ and $E(G^k):= \{uv: u,v\in V(G),\ 1\leq |u,v|\leq k\}$. See \Cref{fig:fig1}.

From the definition, we see that if $d$ is the diameter of a connected graph $G$ (defined as $d:=\max_{u,v\in V(G)} |u,v|$), then $G^d$ is the complete graph on $|V(G)|$ vertices. In some cases, it's natural to exclude complete graphs and hence consider only $G^k$ when $k<d$. Additionally, one may note that if there are two shortest paths (in $G$) between two vertices $u,v$ of length $m> 1$, then $G^m$ may be better viewed as a multigraph where there are two edges between $u,v$. 

\textbf{Notation.} We denote the path graph on $n$ vertices by $P_n$ and the cycle graph on $n$ vertices by $C_n$.

In subsequent sections, we state the generating functions for the number of spanning trees in the graph families 
\begin{align*}
    \mathcal{G}_r&:=\{{C_n}^r\ :\ r < \text{diam } C_n \}\\  \mathcal{H}_r&:=\{{P_n}^r\ :\ r < \text{diam } P_n \}.
\end{align*}
The condition in each construction ensures that our graph families do not contain any "unnatural" complete graphs. For those cases, we can once again recall Cayley's Formula: $\tau(K_n)=n^{n-2}$. Since the diameter of a cycle (resp. path) increases with the number of vertices, the condition $r < \text{diam } C_n = \floor{n/2}$ is implicitly a lower bound on the number of vertices. Explicitly,
\begin{align*}
    \mathcal{G}_r&=\{{C_n}^r\ :\ n\ge 2r+1 \}\\  \mathcal{H}_r&=\{{P_n}^r\ :\ n\ge r+2\}.
\end{align*}
As discussed in the introduction, the initial values of a C-finite sequence determine the numerator of its rational generating function. The minimum values of $n$ above will mark the beginning of that family's sequence.
\begin{figure}[H] 
   \centering
    \input{tikz1}
    \caption{On the left, ${C_7}^{2}$. On the right, ${P_6}^{3}$. The thicker edges represent the edges from the corresponding original graph.}
    \label{fig:fig1}
\end{figure}

% Fun fact due to Omar Garcia: Let n=2k. If k is odd, then the complement of
% {C_n}^{k-2} is a prism graph.
 
 Since paths and cycles are ubiquitous in graph theory, they are the focus of this paper. We provide a quick application below.
 
 
 Let $G$ be a connected graph. Suppose that we wish to estimate the number of spanning trees of its $k$-th power graph, $\tau(G^k)$. One way to estimate $\tau(G^k)$ is to fix a vertex $v\in V(G)$, let vertex sets $H_1,\ldots,H_N$ be the components of $G-v$ and $m_i(v):= \max_{u\in H_i}|u,v|$. Then, deduce the bound:
$$\tau(G^k) \geq \prod_{i=1}^N \tau({P_{m_i(v)}}^k)$$
for all $v$. In particular,
$$\tau(G^k) \geq \max_{v\in V(G)} \prod_{i=1}^N \tau({P_{m_i(v)}}^k).$$
%There are a few questions that arise from this type of estimate: Given a graph $G$, what choice of $v$ maximizes the bound? Which graphs have a "good" choice of $v$? 

% \todo{Cite} \cite{moonlabeltrees} 

\section{Counting Total Number of Leaves} \label{sec:CountingLeaves}
Let $G$ be a graph and $T$ be a spanning tree of $G$. A \textit{leaf} of a tree $T$ is a vertex with degree exactly $1$ in $T$. We write $\cali{L}(T)$ for the set of leaves of $T$ and $\cali{T}(G)$ for the set of (labeled) spanning trees of $G$. When $G$ is clear from context, we simply write $\cali{T}$.


The next proposition plays a key role in our implementation for computing a parameter for graph families that we call the B-Z constant. The idea is to count the total number of leaves (across all spanning trees) in a graph by counting how many times each vertex appears as a leaf. For each vertex in $G$, remove the vertex from $G$ and count the number of spanning trees in the resulting graph. 

\begin{prop}
    If $G$ is a labeled connected simple graph and for $v\in V(G)$, then
    $$\sum_{T\in \cali{T}} |\cali{L}(T)| = \sum_{v\in V(G)} \deg_G(v)\cdot |\cali{T}_v|$$
    where $\cali{T}:=\cali{T}(G)$ and $\cali{T}_v:=\cali{T}(G-v)$. 
\end{prop}
\begin{proof}
     Fix $v\in V(G)$. Write $E_v:=\{e\in E(G)\ :\ v\in e\}$. There is a bijection between $E_v\times \cali{T}_v$ and the spanning trees of $T$ which contain $v$ as a leaf. Hence, we use indicators to obtain
     \begin{align*}
         \sum_{v\in V(G)} \deg_G(v)\cdot |\cali{T}_v| &=  \sum_{v\in V(G)} |\{T\in \cali{T}\ : v\in\cali{L}(T)| \\
         &= \sum_{v\in V(G)}\sum_{T\in \cali{T}} \textbf{1}_{v\in \cali{L}(T)} = \sum_{T\in \cali{T}} |\cali{L}(T)|.
     \end{align*}

\end{proof}
We say $G$ is \textit{vertex-transitive} if for any $u,v\in V(G)$ there is an automorphism $\varphi$ of $G$ such that $\varphi(u)=v$ and $\varphi(v)=u$. 
\begin{cor}\label{cor:vtx-trans}
    If $G$ is vertex-transitive, then
    $$\sum_{T\in \cali{T}} |\cali{L}(T)| = n\cdot \deg_G(v)\cdot |\cali{T}_v|$$
    for any $v\in V(G)$.
\end{cor}

Next, we introduce a parameter for graph families whose member graphs are indexed by number of vertices. For such a graph family, our parameter represents the number of times (on average) that a vertex appears as a leaf in a spanning tree, averaged across all spanning trees, (asymptotically). 

\section{The B-Z Constant: Average Number of Leaves per Vertex}\label{sec:bz-constant}

For a graph family $\cali{G}$ indexed by number of vertices, where $G_n$ represents the graph with $n$ vertices in the family, we call the following the \textit{B-Z constant for} $\cali{G}$:
$$BZ(\cali{G}):=\lim_{n\to\infty}\frac{\sum_{T\in \cali{T}(G_n)} |\cali{L}(T)|}{n\cdot\tau(G_n)}$$
whenever the limit exists. This is the limit of the average number of leaves in a random spanning tree (and normalized by number of vertices) in the discussed family. For the infinite family of complete graphs $K_n$, the limit is famously equal to $1/e$ (see below).
Since the bound $\frac{\sum |\cali{L}(T)|}{n\tau(G)} \le 1$ holds for all $G$, we see that the B-Z constant only fails to exist for those graph families with members whose underlying spanning trees are radically different. The rest of the section provides a few examples of B-Z constants and our approach for computing them.

The B-Z constants for both the family of Cycles and the family of Paths is equal to $0$, since every tree (a path) has a constant number of leaves (two). A star graph is a connected graph where all edges share the same vertex. When $\cali{G}$ is the family of star graphs, its B-Z constant is $1$ because the unique tree of a star graph (itself) has $n-1$ leaves.


Thanks to \Cref{cor:vtx-trans}, computation of the B-Z constant for vertex-transitive graphs is made easier. Our implementation uses this optimization when appropriate. Incidentally, it's easy to compute the B-Z constant for complete graphs by using \Cref{cor:vtx-trans} in conjunction with Cayley's Formula:

\begin{prop}
    The B-Z constant for the graph family $\{K_n\ :\ n\ge3\}$ is
    $\frac{1}{e}$.
\end{prop}
\begin{proof}
    Recall Cayley's formula, which states $\tau(K_n) = n^{n-2}$ for $n\ge 2$. With $\cali{T}:= \cali{T}(K_n)$, \Cref{cor:vtx-trans} tells us that $\sum |\cali{L}(T)| = n\cdot (n-1)^{n-2}$. Hence,
    $$\frac{\sum|\cali{L}(T)|}{n\cdot\tau(K_n)} = \left(\frac{n-1}{n}\right)^{n-2} = \left(1-\frac{1}{n}\right)^{n-2}$$
    which approaches $e^{-1}$ as $n\to\infty$.
\end{proof}

Earlier, we noted that star graphs have B-Z constant equal to $1$. The next proposition observes that we can find a graph family with B-Z constant equal to any rational number (in the interval $[0,1]$) by slightly modifying star graphs.

\begin{prop}\label{prop:star-graph-bz-const}
    For any positive rational number $\frac{p}q < 1$, there is an indexed graph family $\cali{G}$ with $BZ(\cali{G})=p/q$.
\end{prop}
\begin{proof}
    First, we introduce a graph operation called subdivision. Let $e=uv$ be an edge of $G$, with $u,v\in V(G)$. Let $w\not\in V(G)$. The result of subdividing $e$ in $G$ is the graph $G'$ where $V(G') := V(G) \cup \{w\}$ and $E(G') := (E(G)\setminus \{e\})\cup \{uw,wv\}$.

    To construct each member $G_k\in\cali{G}$ (assuming $k\ge 1$): begin with a star graph $S_{pk}$ with $pk$ leaves; then, subdivide $(q-p)k$ edges in $S_{pk}$ and call this $G_k$. Note that $|V(G_k)| = qk+1$ and that $G_k$ has $pk$ leaves. Furthermore, $G_k$ is a tree so it has exactly one spanning tree. It follows that the B-Z constant for $\cali{G}$ is $\lim_{k\to\infty} \frac{pk}{qk+1} = \frac{p}q$.

    
\end{proof}


In upcoming sections, we state the B-Z constants of several graph families. It's possible, as we did in later sections, to compute the B-Z constant of a graph family from its asymptotic behavior in the total number of leaves and number of spanning trees (which can be obtained from their respective generating functions). We used standard residue calculations, implemented in procedure \T{BZc} from our Maple package (\Cref{maple-package}).

% We used our Maple procedure \T{BZc} alongside our graph-generating procedures \T{Hnr} and \T{Gnr} to obtain the results in \Cref{BZ-cycle} and \Cref{BZ-path}. 


\section{Powers of a Cycle: Experimental Results} \label{sec:cycles}
%\todo{Note that the denominator of RGF for $\cali{H}_i$ is always a factor of the denom of RGF for $\cali{F}_i$. Likely due to the former being a subgraph of the latter.}

  % \todo{Notes: Gen funct. for $\cali{G}_6$ may require additional computation time. Seq. of $\cali{G}_4$ not found in OEIS.}

\subsection{Generating Functions for the Number of Spanning Trees}\label{cycle-tree-gf}
In this section, we include our results for the Number of Spanning Trees for the family $\cali{G}_r$, with $2\le r \le 5$.

\begin{thm}
    The generating function $f(t)$ for the number of spanning trees in $\cali{G}_2$ is
    $$\frac{-36t^{5} + 132t^{4} + 46t^{3} - 353t^{2} - 116t + 125}{(t + 1)^{2}(t^{2} - 3t + 1)^{2}}$$
\end{thm}

\begin{thm}
    The generating function $f(t)$ for the number of spanning trees in $\cali{G}_3$ is
    $$\frac{N_3}{ (t - 1)^{2}(t^{4} + 3t^{3} + 6t^{2} + 3t + 1)^{2}(t^{4} - 4t^{3} - t^{2} - 4t + 1)^{2}}$$
    where
    \begin{align*}
        N_3&:=-3072t^{17} + 11683t^{16} + 26868t^{15} + 60636t^{14} - 356682t^{13} - 844329t^{12} - 1651344t^{11} - 104646t^{10} + 813834t^{9} + \\ &3128248t^{8} 
        + 1452330t^{7} + 512250t^{6} - 1392528t^{5} - 1049445t^{4} - 579514t^{3} - 54068t^{2} + 15716t + 16807.
    \end{align*}
    
\end{thm}


\begin{thm}
    The generating function $f(t)$ for the number of spanning trees in $\cali{G}_4$ is
    $$\frac{N_4}{D_4}$$
    where $N_4$ is a polynomial of degree $53$ and
    \begin{align*}
  %      N_4&:= -640000t^{53} + 3750617t^{52} + 10123230t^{51} + 1417153t^{50} + 19407892t^{49} %- 1740647769t^{48} - 3664525174t^{47}\\ 
  %      &- 1281378322t^{46} - 1474725222t^{45} + 130425774277t^{44} + 161571579652t^{43} - 276643639983t^{42} + 127937050526t^{41}\\
  %      &- 2049991617040t^{40} - 4147938524334t^{39} + 6914988457309t^{38} + 2171610912496t^{37} + 9644939666019t^{36}\\
   % &+ 36557666838062t^{35} - 52531258489387t^{34} - 37111231396788t^{33} - 16212599809187t^{32} - 108679784757746t^{31}\\
    %&+ 223245543448335t^{30} + 50901893595560t^{29} + 11312448949745t^{28} + 84184506987858t^{27} - 367100960860495t^{26}\\
    %&+ 31301880304088t^{25} + 8059995095637t^{24} + 20895465258994t^{23} + 241462977425383t^{22} - 72647169201204t^{21}\\
    %&- 20906822167189t^{20} - 32766227152030t^{19} - 62314593399081t^{18} + 26501665160740t^{17} + 12977146508401t^{16}\\
    %&+ 3045687897606t^{15} + 7952556213263t^{14} - 2756400915976t^{13} - 2447122755810t^{12} - 177010550072t^{11}\\
    %&- 328728888428t^{10} + 98055106776t^{9} + 144540407564t^{8} + 18882720344t^{7} + 2102598597t^{6} - 3137317214t^{5}\\
    %&- 2213563334t^{4} - 290464530t^{3} - 42522964t^{2} + 4070186t + 4782969\\
        D_4&=(t + 1)^{2}(t^{6} - 3t^{5} + 6t^{4} - 10t^{3} + 6t^{2} - 3t + 1)^{2}(t^{8} - 4t^{7} - 17t^{6} + 8t^{5} + 49t^{4} + 8t^{3} - 17t^{2} - 4t + 1)^{2}\\ &(t^{12} + 3t^{11} + 12t^{10} + 28t^{9} - 27t^{8} + 36t^{7} - 81t^{6} + 36t^{5} - 27t^{4} + 28t^{3} + 12t^{2} + 3t + 1)^{2}.          
    \end{align*}

 
\end{thm}

\begin{thm}
The generating function $f(t)$ for the number of spanning trees in $\cali{G}_5$ is
    $$\frac{N_5}{D_5}$$
    where $N_5$ is a polynomial of degree $161$ and 
 \begin{align*}
     %N_5&=-248832000t^161 + 1963657584t^160 + 4194274728t^159 - 2032496647t^158 + 75426080792t^157 + 284884355888t^156 - 17020273884786t^155 - 32259840026256t^154 - 52460927780982t^153 - 696146163811972t^152 - 725550654375496t^151 + 26219760321723941t^150 + 9283813674332256t^149 - 49320071066548224t^148 + 794480244967747584t^147 + 978964613497109549t^146 - 14521052864503430056t^145 - 894177689230001812t^144 + 48252416822386418634t^143 - 273043108453098689232t^142 - 572467080016761685482t^141 + 3993851581139799487435t^140 + 266062009522643110720t^139 - 14700762357308700384890t^138 + 45890407655248774916472t^137 + 127650512869807009046928t^136 - 598213294456279482688854t^135 + 10465999224552222981901t^134 + 1879101191014314192612616t^133 - 3900257353683237367579172t^132 - 14414402528103229252833942t^131 + 55298060156739954979558656t^130 - 20375877576112606731723918t^129 - 111900276543887915404203788t^128 + 229214207805069894597390376t^127 \\ &+ 671520209965461953647972414t^126 - 2688823143195025638484277832t^125 + 1731541133831635370426702448t^124 + 3330493668032112602099501094t^123 - 8246933357326057817312367303t^122 - 16679812588976770321032903024t^121 + 73918856527950114038384975157t^120 - 59462617356214134570121184670t^119 - 50455463720316492163276123536t^118 + 174013931216313370420658908422t^117 + 251653695492186053842626957480t^116 - 1257099136018116260910239390664t^115 + 1068308614221141563927385498594t^114 + 371784843893001450112575887238t^113 - 2135147974459460383649585688384t^112 - 2583158624525409687892437631626t^111 + 13851329107415923977263314050696t^110 - 10999205756329419964361816342520t^109 - 550788013954062846351670861746t^108 + 15439961455946054213464964126298t^107 + 19933210509524749011298907239056t^106 - 102864504755213071945644354921906t^105 + 62409302806638304975781569039640t^104 - 13363752087042160124337333512008t^103 - 57718111815162451256109766308598t^102 - 102691382446613825578916562346338t^101 + 528755976520196627631061929512832t^100 - 178524412821349876422364334021658t^99 + 98007390649768215617561091382202t^98 + 23568330209040119006174708003384t^97 + 297869164308437820228923148333494t^96 - 1794747224561943114760694511813402t^95 + 229574708671509279525062897116176t^94 - 410017522318052489351696508109974t^93 + 379534144914488212623685088132480t^92 - 370010046364659615633890243930968t^91 + 4184803547786165819150271564446012t^90 + 30808011499154554851247603237014t^89 + 1055679249696494520772867746483072t^88 - 1107024719169772753422009607571946t^87 + 75000007032475436428076064064978t^86 - 6999078253052927478788111778058184t^85 - 566717851984974334583451481048586t^84 - 1748022887671391426612499603146130t^83 + 1607515438127554142752107250326960t^82 + 150925418900405736523131085643874t^81 + 8346137850651287231466149263910974t^80 + 882911530071755825743607168107576t^79 + 1896675318016809937790004284181334t^78 - 1477408490483544262753957873043106t^77 + 33199575128343087875798703757056t^76 - 7003765793932462368309531315177150t^75 - 565266616576537189951271871475646t^74 - 1285773701741464762931863012719080t^73 + 910767970071720206098789882015006t^72 - 324850785645941464890162113501658t^71\\
      %&+ 4189928736714587984356704609960816t^70 + 43482095528646801338198296632090t^69 + 430329762102200076954596658730424t^68 - 387394888810491489841871286480184t^67 + 382351663024493509568612053616558t^66 - 1785767160749773297608065783442642t^65 + 101659696421413382493359247116064t^64 + 23336467112707963462897704784674t^63 + 119688557143595674140667727106602t^62 - 222868913428352755878056583749656t^61 + 515806422701247975330723137537408t^60 - 40544357833186052498076267565458t^59 - 60497691069399340993212253893264t^58 - 26659041003944107647213165923742t^57 + 70650439602997268636407891602992t^56 - 97386448129189825492019941697560t^55 + 7718852297739146772089990761598t^54 + 16306841556085076958453543339882t^53 + 2406595660843151850193165491744t^52 - 12234797105942235569405518147422t^51 + 12807737662096956486922758384960t^50 - 966737707693205690187195105768t^49 - 2276476353422989193961258964014t^48 + 9389264409194265704408706582t^47 + 1204935328651988679803582192976t^46 - 1153987811415912950574780880758t^45 + 108062476548546606546519937152t^44 + 190863615529928672225110296168t^43 - 23321755680001034664735531402t^42 - 69950405834356985856983020110t^41 + 68156177778708080091371218800t^40 - 8420712707315106012134480598t^39 - 9501367157391272958927104715t^38 + 2112249158282059145986036944t^37 + 2249427931822604975550638490t^36 - 2518200413299028555614082676t^35 + 374543384176086965857979232t^34 + 281235627884111453627006676t^33 - 79174398517080720020435108t^32 - 34876830335155008477364544t^31 + 53094389244461298349829503t^30 - 8253638847757506310132998t^29 - 4983957519313664051410848t^28 + 1337432449160541218448642t^27 + 218822934774110700936745t^26 - 588730461352364865014384t^25 + 59072210059642063080190t^24 + 53733631959181055774616t^23 - 8922529109102454087168t^22 - 1116646465912310695440t^21 + 3941108835166048697647t^20 - 117196645913298608984t^19 - 290145971426701996604t^18 + 17158139216674293114t^17 + 2453189726804992848t^16 - 14415563168531272260t^15 - 664300906124185063t^14 + 725871940133709824t^13 + 26943639129911366t^12 + 9522586356425952t^11 + 27549131432584944t^10 + 2332231658845500t^9 - 436372250830996t^8 - 93364112005072t^7 - 40563010269100t^6 - 21817120471590t^5 - 2095363792560t^4 - 152840200848t^3 - 20396723899t^2 + 1872418472t + 2357947691\\
     D_5&=(t - 1)^{2}(t^{8} + 3t^{7} + 6t^{6} + 10t^{5} + 15t^{4} + 10t^{3} + 6t^{2} + 3t + 1)^{2}(t^{8} + 3t^{7} + 6t^{6} - t^{5} + 15t^{4} - t^{3} + 6t^{2} + 3t + 1)^{2}\\
     &(t^{16} - 5t^{15} + 10t^{14} - 10t^{13} - 28t^{12} + 10t^{11} + 110t^{10} + 110t^{9} + 88t^{8} + 110t^{7} + 110t^{6} + 10t^{5} - 28t^{4} - 10t^{3} + 10t^{2}\\
     &- 5t + 1)^{2}(t^{16} - 5t^{15} - 23t^{14} - 10t^{13} - 94t^{12} - 485t^{11} + 242t^{10} + 110t^{9} + 649t^{8} + 110t^{7} + 242t^{6} - 485t^{5} - 94t^{4}\\
     &- 10t^{3} - 23t^{2} - 5t + 1)^{2}(t^{32} + t^{31} + 12t^{30} + 45t^{29} + 45t^{28} - 1561t^{27} + 3917t^{26} - 3222t^{25} - 3981t^{24} + 7745t^{23}\\
     &+ 26379t^{22} - 88937t^{21} + 84093t^{20} + 63864t^{19} - 153881t^{18}- 202281t^{17} + 550163t^{16} - 202281t^{15} - 153881t^{14}\\
     &+ 63864t^{13} + 84093t^{12} - 88937t^{11} + 26379t^{10} + 7745t^{9} - 3981t^{8} - 3222t^{7} + 3917t^{6} - 1561t^{5} + 45t^{4} + 45t^{3}\\
     &+ 12t^{2} + t + 1)^{2}.
 \end{align*}
\end{thm}
\subsection{Generating functions for the Total Number of Leaves} \label{cycle-leaf-gf}
\begin{thm}
    The generating function for the total number of leaves (across all spanning trees of a member) in $\cali{G}_2$ is
    $$\frac{-8(10t^7 - 67t^6 + 109t^5 + 99t^4 - 282t^3 - 30t^2 + 145t - 40)}{(t + 1)^2(t^2 - 3t + 1)^3}.$$
\end{thm}

\begin{thm}
The generating function for the total number of leaves (across all spanning trees of a member) in $\cali{G}_3$ is
    $$\frac{A_3}{(t - 1)^3(t^4 + 3t^3 + 6t^2 + 3t + 1)^3(t^4 - 4t^3 - t^2 - 4t + 1)^3}$$
where 
\begin{align*}
    A_3&:=-8820t^{26} + 51390t^{25} + 61812t^{24} + 2088t^{23} - 2539950t^{22} - 2981160t^{21} + 2492784t^{20} + 45845688t^{19}\\ 
    &+ 83018808t^{18}+ 107694630t^{17} - 44892840t^{16} - 166389300t^{15} - 333210654t^{14} - 121438506t^{13} + 42702660t^{12}\\ 
    &+ 312824052t^{11}+ 213402930t^{10} + 100784592t^9 - 77616756t^8 - 90041700t^7 - 62209728t^6 - 13836186t^5\\
    &+ 276924t^4 + 2761596t^3+ 501534t^2 + 32592t - 54432.
\end{align*}
\end{thm}
As the reader might have noticed, the numerators for these generating functions become too cumbersome to write (and more quickly than in the previous section). Henceforth, we omit the numerator and refer the reader to this website \cite{spt} for detailed results when $4\leq r\leq 5$.

\begin{thm}
The generating function for the total number of leaves (across all spanning trees of a member) in $\cali{G}_4$ is
    $$\frac{A_4}{B_4}$$
where $A_4$ is a polynomial of degree $80$ and 
\begin{align*}
    B_4&= (t + 1)^3(t^6 - 3t^5 + 6t^4 - 10t^3 + 6t^2 - 3t + 1)^3(t^8 - 4t^7 - 17t^6 + 8t^5 + 49t^4 + 8t^3 - 17t^2 - 4t + 1)^3\\
    &(t^{12} + 3t^{11} + 12t^{10} + 28t^9 - 27t^8 + 36t^7 - 81t^6 + 36t^5 - 27t^4 + 28t^3 + 12t^2 + 3t + 1)^3
\end{align*}

\end{thm}




\subsection{B-Z Constants} \label{BZ-cycle}
See \Cref{sec:bz-constant} to read about our method for computing these constants. Recall that $BZ(\cali{G})$ denotes the B-Z constant of a graph family $\cali{G}$.

\begin{thm}
    The B-Z constant for $\cali{G}_2$ is 
    $$-6+\frac{14\sqrt{5}}{5}.$$
\end{thm}
\begin{thm}
    The B-Z constant for $\cali{G}_3$ is 
    $$\frac37 \left(\frac{45}2 + 9 \sqrt{7} - \frac12 \sqrt{3857 + 1684 \sqrt{7}}\right).$$
\end{thm}

\begin{thm}
    Let $\alpha$ be the smallest real root of $z^8-4z^7-17z^6+8z^5+49z^4+8z^3-17z^2-4z+1$. Then, the B-Z constant for $\cali{G}_4$ is 
%    $$-\frac8{75}\cdot\alpha^7-\frac{2144}{2025}\cdot\alpha^6+\frac{1816}{225}\alpha^5+\frac{41056}{2025}\alpha^4-\frac{632}{75}\alpha^3-\frac{29312}{675}\alpha^2-\frac{25304}{2025}\alpha+\frac{6944}{2025}$$
   $$\frac{1}{2025}\left(-216\alpha^7-2144\alpha^6+16344\alpha^5+41056\alpha^4-17064\alpha^3-87936\alpha^2-25304\alpha+6944\right).$$
\end{thm}
\begin{cor}
    $$BZ(\cali{G}_3) < \frac{117451}{355635} < BZ(\cali{G}_4) < \frac{117452}{355635}$$
\end{cor}
In the previous theorem, $\alpha \approx 0.158778$.

\section{Powers of a Path: Experimental Results} \label{sec:paths}
\subsection{Generating functions for the Number of Spanning Trees} \label{path-tree-gf}
In this section, we include our results for the Number of Spanning Trees in the class $\cali{H}_r$, with $2\le r \le 6$.

\begin{thm}
    The generating function $f(t)$ for the number of spanning trees in $\cali{H}_2$ is
    $$\frac{-3t+8}{t^{2} - 3t + 1}.$$
\end{thm}
   
\begin{thm}
    The generating function $f(t)$ for the number of spanning trees in $\cali{H}_3$ is
   $$\frac{-16t^4 + 77t^3 - 33t^2 + 39t - 75}{(t - 1)(t^{4} - 4t^{3} - t^{2} - 4t + 1)}.$$
\end{thm}

\begin{thm}
    The generating function $f(t)$ for the number of spanning trees in $\cali{H}_4$ is
   $$\frac{M_4}{(t^{6} - 3t^{5} + 6t^{4} - 10t^{3} + 6t^{2} - 3t + 1)(t^{8} - 4t^{7} - 17t^{6} + 8t^{5} + 49t^{4} + 8t^{3} - 17t^{2} - 4t + 1)}.$$
   where 
   \begin{align*}
       M_4&=-125t^{13} + 859t^{12} - 13t^{11} - 3141t^{10} + 3475t^9 - 5968t^8 - 11312t^7 \\
       &+ 36080t^6 - 5597t^5 - 7893t^4 + 2435t^3 - 2741t^2 - 413t + 864\\
   \end{align*}
\end{thm}

We know the generating functions for larger $r$ values, but there are many terms with longer coefficients. So, we do not state them in the paper. They are stated in this website \cite{spt}.

\begin{thm}
    The generating function $f(t)$ for the number of spanning trees in $\cali{H}_5$ is
   $$\frac{M_5}{E_5}.$$
   where 
   $M_5$ is a degree $40$ polynomial in $t$ and
   \begin{align*}
       E_5&=(t - 1)(t^{8} + 3t^{7} + 6t^{6} - t^{5} + 15t^{4} - t^{3} + 6t^{2} + 3t + 1)(t^{16} - 5t^{15} + 10t^{14} - 10t^{13} - 28t^{12}\\
       & + 10t^{11}+ 110t^{10} + 110t^{9} + 88t^{8} + 110t^{7} + 110t^{6} + 10t^{5} - 28t^{4} - 10t^{3} + 10t^{2} - 5t + 1)(t^{16}\\
       &- 5t^{15} - 23t^{14}- 10t^{13} - 94t^{12} - 485t^{11} + 242t^{10} + 110t^{9} + 649t^{8} + 110t^{7} + 242t^{6} - 485t^{5}\\
       &- 94t^{4} - 10t^{3} - 23t^{2}- 5t + 1)    
   \end{align*}
\end{thm}



%\todo{Seq. of span. trees for $\cali{H}_3, \cali{H}_4$ not found in OEIS.}

\subsection{Generating functions for the Total Number of Leaves} \label{path-leaf-gf}

\begin{thm}
The generating function for the total number of leaves (across all spanning trees of a member) in $\cali{H}_2$ is
    $$\frac{-2(2t^3 - 15t^2 + 27t - 9)}{(t^2 - 3t + 1)^2}$$
\end{thm}

\begin{thm}
The generating function for the total number of leaves in $\cali{H}_3$ is
    $$\frac{2(16t^{10}-154t^9+403t^8-340t^7+963t^6-768t^5+1109t^4-788t^3+509t^2-470
t+96)}{(t-1)^2(t^4-4t^3-t^2-4t+1)^2}$$
\end{thm}

\begin{thm}
The generating function for the total number of leaves in $\cali{H}_4$ is
    $$\frac{C_4}{(t^6 - 3t^5 + 6t^4 - 10t^3 + 6t^2 - 3t + 1)^2(t^8 - 4t^7 - 17t^6 + 8t^5 + 49t^4 + 8t^3 - 17t^2 - 4t + 1)^2}$$
    where $C_4$ is a degree $29$ polynomial. Note that the degree of the numerator is $28.$
\end{thm}


\subsection{B-Z Constants} \label{BZ-path}
See \Cref{sec:bz-constant} to read about our method for computing these constants. Compare the results in this section to \Cref{BZ-cycle}. 


\begin{thm}
    The B-Z constant for $\cali{H}_2$ is 
    $$-6+\frac{14\sqrt{5}}{5}.$$
\end{thm}
\begin{thm}
    The B-Z constant for $\cali{H}_3$ is 
    $$\frac37 \left(\frac{45}2 + 9 \sqrt{7} - \frac12 \sqrt{3857 + 1684 \sqrt{7}}\right).$$
\end{thm}

\begin{thm}
    $BZ(\cali{H}_4)=BZ(\cali{G}_4)$.
\end{thm}

We also verified that $BZ(\cali{H}_5)=BZ(\cali{G}_5)$. See \cite{spt}.

\section{B-Z Constants for Grid and Torus Graphs}\label{sec:gridtorus}
In previous sections, we discussed powers of cycles and powers of paths. The members of these two graph families were related by a subgraph relation and we found their B-Z constants to be the same up to $r=5$. Since a power of a cycle is vertex-transitive, computing the total number of leaves was faster (\Cref{cor:vtx-trans}). In this section, we discuss another pair of graph families -- Grid Graphs and Torus Graphs -- which are also related by a subgraph relation. Similarly to the previous pair of families, Torus graphs are vertex-transitive.  However, the B-Z constants for grid graphs and torus graphs differ.

\textbf{Definition.} The $a\times b$ grid graph $P_a\times P_b$ has vertex set $V(P_a\times P_b):=\{(i,j)\ :\ i\in[a], j\in[b]\}$ and two (distinct) vertices $(u_1,u_2)$ and $(v_1,v_2)$ are adjacent whenever $|u_1-v_1|=1$ or $|u_2-v_2|=1$, but not both.

\textbf{Definition.} The $a\times b$ torus graph $C_a\times C_b$ has vertex set $V(C_a\times C_b):=\{(i,j)\ :\ i\in[a], j\in[b]\}$ and two (distinct) vertices $(u_1,u_2)$ and $(v_1,v_2)$ are adjacent whenever $|u_1-v_1|\in\{1,a-1\}$ or $|u_2-v_2|\in\{1,b-1\}$, but not both.

\begin{figure}[H] 
   \centering
    \input{tikz2}
    \caption{On the left, the $3\times 3$ Grid Graph. On the right, the $3\times 3$ Torus Graph.}
    \label{fig:fig2}
\end{figure}

For the family of torus graphs, we assume $\min(a,b) \ge 3$ to avoid considering multigraphs. A torus graph (resp. grid graph) with dimensions $a\times b$ is isomorphic to another torus graph (resp. grid graph) with dimensions $b\times a$; hence, we may treat the two interchangeably. 

\begin{thm}
    The B-Z constant for the family of $2\times n$ grid graphs is
    $$\sqrt{3}-\frac{3}{2}.$$
\end{thm}

In the $3\times n$ case, the B-Z constants of the two corresponding families differ.   

\begin{thm} \label{torus3}
    The B-Z constant for the family of $3\times n$ torus graphs is
    $$\frac{24\sqrt{21}-104}{21}.$$
\end{thm}
%\begin{thm}
%    Let $\alpha$ be the smallest real root of $z^4-15z^3+32z^2-15z+1$.  The B-Z constant for the family of $3\times n$ grid graphs is
%    $$\frac{-7\alpha^3 +143\alpha^2 -1027\alpha+248}{630}\in\left[\frac{729973}{2753265},\frac{729974}{2753265}\right].$$
%\end{thm}


\begin{thm} \label{grid3}
    The B-Z constant for the family of $3\times n$ grid graphs is
    $$\frac{-10500 + 2200 \sqrt{21} + 1197 \sqrt{230 - 50 \sqrt{21}} + 149 \sqrt{210 (23 - 5 \sqrt{21})}}{5040}.$$
\end{thm}

Similarly, in the case of $4\times n$ grid and torus graph, their B-Z constants differ again \cite{spt}. We conjecture that they differ for all $r\times n$ when $r\ge 3$.  

The algebraic numbers of the families above increase in complexity as the fixed dimension of the corresponding family increases. In this website \cite{spt}, we recorded the outputs of these results -- symbolically and numerically. We summarize some of those results here, with decimal approximations (and at least six digits):

The B-Z constant for: $4\times n$ torus graphs is $0.2917148\ldots$; $5\times n$ torus graphs is $0.29342497\ldots$; and $6\times n$ torus graphs is $0.294011\ldots$.
The B-Z constant for $4\times n$ grid graphs is $.2746417\ldots$. 

We computed B-Z constants for fewer grid families (than torus families) because grid graphs are not vertex-transitive; hence, we were unable to apply \Cref{cor:vtx-trans} to speed up computation of the "total number of leaves".

\section{Verification of Results by Random Sampling}\label{sec:verification}

In our implementation, we wrote a procedure to compute the total number of leaves of a graph (\texttt{NumLeaves} or \texttt{VtxTransNumLeaves}) and another to compute the number of spanning trees (\texttt{NumSpanTree}). The ratio between the outputs of these procedures is the average number of leaves of a graph. 

To verify the accuracy of these procedures, we selected a large member from each of our graph families (at least $100$ vertices) and then sampled a large number of spanning trees from that graph (at least $100$ and usually more than $200$). After doing so, we computed the average number of leaves of the graph in the sample and compared it to our procedures' exact computation. In all cases, we found that the estimate and the true values were similar. For more detailed results on this verification, we direct the reader to \cite{spt}.

The algorithm we used to sample uniformly random spanning trees is Wilson's Algorithm, as described in \cite{wilsonalg}.

\section{Accompanying Maple package} \label{maple-package}
In the following procedures, graphs are represented as an \T{exprseq} type in Maple. Particularly, a graph is \T{n,E}, where \T{n} is a positive integer and \T{E} is a set of edges on $[n]$. We assume all graphs are connected.

Our Maple package broadly depends on the \texttt{LinearAlgebra} library. The \texttt{RandomTree} procedure also makes use of the \texttt{GraphTheory} library. Below we list some key procedures along with their descriptions:
%%%%%%%%%%% 

\texttt{NumSpanTree(n,E)} given a positive integer \texttt{n} and a set of edges \T{E} on the set $\{1,\ldots,n\}$, the procedure returns the number of spanning trees of the corresponding graph $n,E$.

\texttt{NumSpanTreeSeq(F, ArgList, a,b)} given the name of a graph-generating procedure \T{F} and a list of arguments \T{ArgList}, outputs a list of the number of spanning trees for the graphs \T{F(a, op(ArgList))},$\ldots$,\T{F(b, op(ArgList))}. 

%%%%%%%%%%

\T{NumLeaves(n,E)} given a graph \T{n,E}, returns the total number of leaves in such a graph across all its spanning trees.

\T{NumLeavesSeq(F, ArgList, a,b)} given the name of a graph-generating procedure \T{F} and a list of arguments \T{ArgList}, outputs a list of the total number of leaves for the graphs \T{F(a, op(ArgList))},$\ldots$,\T{F(b, op(ArgList))}. 

\T{VtxTransNumLeavesSeq(F, ArgList, a,b)} similar to \T{NumLeavesSeq}. However, assumes that the graphs generated by \T{F} are vertex-transitive. Uses \Cref{cor:vtx-trans} to compute the output faster.

%%%%%%%%%%%%%%

\T{Hnr(n,r)} constructs the $r$-th power of a path on $n$ vertices. Returns $n,E$.

\T{Gnr(n,r)} constructs the $r$-th power of a cycle on $n$ vertices. Returns $n,E$.

%%%%%%%%%%%%%%%%%

\T{BZc(F,Arglist,a,b,k)} Using a graph-generating procedure \T{F} with fixed arguments \T{ArgList} and varying the first argument from \T{a} to \T{b}, compute the B-Z constant. \T{k} adjusts the B-Z computation so that if the index of a graph (in the family) is $n$, then the graph has $k\cdot n$ vertices.

The following procedures generate the outputs for the (main) theorems in this paper, up to \T{R} $\ge 2$, with \T{K} terms in the sequence, and in variable \T{x}: 

\T{HnrS(R,x,K)}

\T{GnrS(R,x,K)}


From Doron Zeilberger's \T{Cfinite.txt} package: 

\T{RGF(S,t)} given a C-finite sequence \T{S}, outputs its rational generating function in the variable \T{t}.

\section{Conjectures and Further Discussion} \label{sec:conj}
Some observations from our results may indicate deeper structural insights:
\begin{enumerate}
    \item For each $r$ we computed, the denominator of a rational function from \Cref{path-tree-gf} divides the (corresponding) denominator of a rational function from \Cref{cycle-tree-gf}. Similarly for \Cref{path-leaf-gf} and \Cref{cycle-leaf-gf}.  
        \item In the denominators for the generating functions given in \Cref{cycle-tree-gf}, \Cref{cycle-leaf-gf}, \Cref{path-tree-gf}, \Cref{path-leaf-gf}, each polynomial factor has coefficients which are symmetric. Is this also true for all other recursive graph families?
\end{enumerate}

While in this paper we mainly provided results for powers of cycles and powers of paths, we also computed the corresponding rational generating functions for Grid Graphs and Torus (Grid) Graphs (see \cite{spt}). Those two classes of families, when compared to each other, did not satisfy property 1.; however, they did satisfy property 2 (as listed above). Since a grid graph is a subgraph of a torus graph (of the same dimensions), we know that property 1. is not satisfied from just a subgraph relation. We conclude with a few conjectures. \newpage

\begin{conj}
    The B-Z constants of $\cali{G}_r$ and $\cali{H}_r$ are equal for all $r\ge 1$.
\end{conj}

Assuming that the previous conjecture holds, a natural question arises: given a graph family, is there a threshold for how many vertices you can "modify" (by edge deletion) while keeping the same B-Z constant? It turns out that Grid graphs and Torus Graphs have different B-Z constants, which may suggest that we can only modify a finite number of vertices. Originally, we considered the following conjecture. Note that the conditions in the following conjecture are satisfied when $\cali{G}=\cali{G}_r$ and $\cali{H}=\cali{H}_r$ (as defined in \Cref{graph-fams}).

\begin{conj}
    \textbf{\emph{(False)}} Let $\cali{G}:=\{G_n\}_n$ and $\cali{H}:=\{H_n\}_n$ be (indexed) families of connected graphs, such that $BZ(\cali{G})$ and $BZ(\cali{H})$ both exist. If the following hold:
    \begin{itemize}
        \item $H_n\subseteq G_n$ for all $n$ and
        \item there is some $c_1$ for which  $|E(G_n\setminus H_n)|\leq c_1$ for all $n$,
    \end{itemize}
   then $\cali{G}$ and $\cali{H}$ have the same B-Z constant. 
\end{conj}


For two graphs $G,H$ such that $V(G)=V(H)$, we define $G\setminus H$ as the graph $V(G\setminus H):=V(G)$ and $E(G\setminus H):=E(G)\setminus E(H)$. Unfortunately, the conjecture above fails for families of sparse graphs, as proven by considering the following counterexample.

\textbf{Counterexample.} Let $\cali{H}$ be the family of graphs constructed in the proof of \Cref{prop:star-graph-bz-const} with B-Z constant equal to $\frac12$. In other words, $\cali{H}$ is the family of graphs resulting from subdividing each edge in a star graph once. From each $H_n\in \cali{H}$, construct $G_n$ by adding an edge between two non-leaf vertices. We see that $\tau(G_n)=3\cdot\tau(H_n)$, but $\cali{L}(G_n)=\cali{L}(H_n)$. Hence, $BZ(\cali{G})=\frac{1}{3}\cdot BZ(\cali{H}) = \frac16 \neq \frac12 = BZ(\cali{H})$. 


\begin{obs}
    Let $n\ge 2r+1$. If $G_n\in \cali{G}_r$ and $H_n\in \cali{H}_r$, then $G_n\setminus H_n$ contains a (copy of the) Half Graph on $2r$ vertices and $n-2r$ isolated vertices.
\end{obs}
The \textit{Half Graph} on $2n$ vertices is a bipartite graph with vertex set $\{u_1,\ldots,u_n,v_1,\ldots,v_n\}$ and edges $\{u_iv_j\ :\ i\leq j\}$. Since $r$ is fixed, the number of differing edges between a Power of a Cycle and a Power of a Path is finite.

\typeout{get arXiv to do 4 passes: Label(s) may have changed. Rerun}

\bibliographystyle{abbrv}
 \input{references.bbl}
%\bibliography{ref}

\end{document}