\input{stuff}
\title{\vspace{-0.8cm} Automated  Counting of Spanning Trees for  Several Infinite families of Graphs}
%setcounter{secnumdepth}{0} % DISABLES SECTION NUMBERING
% Experimental Study: 
% proposal: automatic enumeration of spanning trees and an asyno
\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 rational generating function for sequences related to spanning tree enumeration. 
Said families are Powers of Cycles, Powers of Paths, and (later) 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 implies that the generating function is guaranteed to be a rational function. 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 generate sufficiently many terms. and then fit the data into a rational function,
and everything can be proved rigorously {\it 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 asympotic for the average number of leaves per vertex in a random spanning tree in each family that always tends
to a certain number, that we compute explicitly. This number, that we chisten the B-Z constant of the infinite family is always a certain (often coplicated) algebraic number, in contrast
to the family of complete graphs (i.e. all trees) where this constant is (the transcedental number) $1/e$.
    \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 will contain several spanning trees. When we count the number of spanning trees of a graph in this paper, we will 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 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 given by taking 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 will be 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 will state the value $a_0$ of our sequence to disambiguate $p(x)$ in the sequence's rational generating function. 

 Due to the recursive nature of the graph families we will be considering, we can 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 will be 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 will apply Kirchhoff's Matrix Tree Theorem, which allows us to compute the number of spanning trees of a(n $n$-vertex graph) 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 will describe similar methods that we used to counting total number of leaves (across all spanning trees) for members in the same families. In addition, we consider an asymptotic constant relating total leaves to total spanning trees in any families (for which the constant is well-defined). Finally, we include experimental verification of our results' correctness and a description of the accompanying Maple package that we used. Additional outputs and code will be available at \cite{spt}.


% \todo{Can we use the generating functions to obtain asymptotic lower bounds? Is this even a good idea or are there better known bounds on power graphs? Note that our results are only limited such that $k\le 7$ or something [TBD].}


\section{Preliminaries and Graph Families}
For ease of notation, we assume all graphs are simple.

\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 $|u,v|=\infty$ and say the distance between them is infinite.

\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$, that is $d:=\max_{u,v\in V(G)} |u,v|$. Then, $G^d$ is the complete graph on $|V(G)|$ vertices. Later in the paper, we will only consider $G^k$ where $k<d$ for this reason.

\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. The number of spanning trees in a complete graph on $n$ vertices is given by Cayley's formula to be $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 determines the numerator in its rational generating function. Hence, for the generating functions below in the rest of the paper, we will begin every sequence at $n=2r+1$ for $\cali{G}_r$ and at $n=r+2$ for $\cali{H}_r$.
\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: 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, we have focused on them in this paper. Let $G$ be a connected graph. Suppose that we wish to estimate the complexity (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 $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{[To Z: Could we try answering this later?]}

 \todo{Cite} \cite{moonlabeltrees} 

\section{Counting Total Number of Leaves} 
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 the tree. Denote by $\cali{L}(T)$, the set of leaves of $T$. For ease of notation, we will write $\cali{T}(G)$ for the set of (labeled) spanning trees of $G$ and will shorten this as $\cali{T}$ whenever $G$ is clear from context.


The next proposition plays a key role in our implementation for computing a parameter of a graph we later call the B-Z constant. The idea is to count the total number of leaves (across all spanning trees) in a graph by removing a vertex and finding a spanning tree of 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{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{count-leaves}

For a graph family indexed by number of vertices, $\cali{G}$, where $G_n$ represents the $n$-th graph in the family, we call the following the \textit{B-Z constant for} $\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 in the discussed family, that for the infinite families of complete graphs $K_n$ is famously (see below) is $1/e$.
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$. When $\cali{G}$ is the family of star graphs, its B-Z constant is $1$. \todo{[Include a brief interpretation/intuition]}


Thanks to \Cref{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{vtx-trans} in conjunction with Cayley's Theorem:

\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{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]$) if we slightly modify star graphs.

\begin{prop}
    For any positive rational number $\frac{p}q < 1$, there is an indexed graph family $\cali{G}$ which has B-Z constant equal to $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\}$.

    We will construct $\cali{G}$ by constructing each member $G_k\in \cali{G}$. For each integer $k\geq 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}


Later, we will state the B-Z constants of several families we mentioned here. 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 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}
%\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}
In this section, we include our results for the Number of Spanning Trees of the class $\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}
\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 will eventually 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{count-leaves} to read about our method for computing these constants. Let $BZ(\cali{G})$ denote 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}
\subsection{Generating functions for the Number of Spanning Trees}
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}

\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}

Note: the numerator and denominator in the following have the same degree.
\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{count-leaves} 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}

\todo{ [The B-Z constants up to $\cali{H}_5$ and $\cali{G}_5$ are actually equal] }

\section{Verification of Results by Random Sampling}

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}
In the following procedures, graphs will be 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:
%%%%%%%%%%% Alter the order these procedures are listed as you wish

\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{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 theorems in this paper: \todo{[Add these]}

\T{HnrS}

\T{GnrS}


From Doron Zeilberger's \T{Cfinite.txt} package: \todo{[Dr. Z, add more if necessary:]}

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

\section{Questions and Conjectures}

\todo{[To Z: Instead of writing these fully, I'm loosely listing them so you can decide which ones to keep.]}

Why are the coefficients for the polynomials in the denom. of RGFs for Hnr and Gnr symmetric? Why do the denoms of the RGFS of Hnr divide those of Gnr? (Related to Eugene Zima Question).

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


Let $\Delta(G)$ denote the maximum degree in a graph. $G_n\setminus H_n$ \todo{[define this appropriately]}

\begin{conj}
    Let $\cali{G}:=\{G_n\}_n$ and $\cali{H}:=\{H_n\}_n$ be (indexed) graph families. If $H_n\subseteq G_n$ for all $n$, the number of vertices with positive degree in $G_n\setminus H_n$ is bounded, and $\Delta(G_n\setminus H_n)$ is bounded; then, $\cali{G}$ and $\cali{H}$ have the same B-Z constant. 
\end{conj}

\todo{[Eugene Zima question about RGF factors]}


%Can you find a natural family $\cali{G}$ of graphs (ordered by number of vertices) whose spanning tree sequence consists of the Fibonacci numbers and $\cali{G}$ is not all cycles?
%(I think no. It could probably be proved with some algebra or number theory. The first few graphs are forced to be cycles.)


 
\bibliographystyle{abbrv}
\bibliography{ref}

\end{document}