Automated Counting of Spanning Trees for Several Infinite families of Graphs

Pablo Blanco  Doron Zeilberger

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 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.

1 Introduction and Background

A subgraph T of a graph G such that T is a tree with V (T) = V (G) is called a 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 τ(G). Cayley’s formula counts the number of spanning of a complete graph on n vertices to be n^{n−2} = τ(K_{n}).

The generating function f(x) for a sequence (a_{0}, a_{1}, …) is the formal power series given by taking the sequence terms as its coefficients:

f(x) := ∑_{n=0}^{∞} a_{n}x^{n}.

Whenever a sequence has a recurrence of finite length, with constant coefficients, it is called C-finite. In other words, (a_{0}, a_{1}, …) is C-finite (of order r) if there is a fixed r and coefficients c_{0}, …, c_{r−1} with c_{0} ≠ 0 such that

a_{n+r} = c_{r−1}a_{n+r−1} + … + c_{0}a_{n}

for all n ≥ 0.

The following will be a useful property of C-finite sequences:

Theorem 1.0.1. [? ][Kauers-Paule, Thm. 4.3] A sequence (a_{0}, a_{1}, …) is C-finite (of order r) with recurrence

a_{n+r} = c_{r−1}a_{n+r−1} + … + c_{0}a_{n}

if and only if

∑ a_{n}x^{n} = \frac{p(x)}{1 − c_{r−1}x + … − c_{1}x^{r−1} − c_{0}x^{r}}

for some polynomial p(x) of degree at most r − 1.

In fact, the polynomial p(x) in the previous Theorem is determined by the initial values (a_{0}, …, 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 [? ] 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 [? ], called 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}, …, v_{n}, its Laplacian matrix is a symmetric matrix with its entries defined by

a_{i,j} := \begin{cases}−1 & if v_{i} ∼ v_{j} and i ≠ j \\ deg(v_{i}) & if i = j \end{cases} .

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 [? ].

2 Preliminaries and Graph Families

For ease of notation, we assume all graphs are simple.

Definition. For a graph G, the 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| = ∞ and say the distance between them is infinite.

Definition. Let G be a graph. For an integer k ≥ 1, the k-th 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 ∈ V (G), 1 ≤ |u, v| ≤ k}. See Figure 1.

From the definition, we see that if d is the diameter of a connected graph G, that is d := max_{u,v∈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.

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

G_{r} := {C_{n}^{r} : r < diam C_{n}}
H_{r} := {P_{n}^{r} : r < diam P_{n}}.

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 < diam C_{n} = ⌊n/2⌋ is implicitly a lower bound on the number of vertices. Explicitly,

G_{r} = {C_{n}^{r} : n ≥ 2r + 1}
H_{r} = {P_{n}^{r} : n ≥ r + 2}.

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 G_{r} and at n = r + 2 for H_{r}.

Figure 1: On the left, C_{7}^{2}. On the right, P_{6}^{3}. The thicker edges represent the edges from the corresponding original 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, τ(G^{k}). One way to estimate τ(G^{k}) is to fix a vertex v ∈ V (G), let H_{1}, …, H_{N} be the components of G − v and m_{i}(v) := max_{u∈H_{i}} |u, v|. Then, deduce the bound:

τ(G^{k}) ≥ ∏_{i=1}^{N} τ(P_{m_{i}(v)}^{k})

for all v. In particular,

τ(G^{k}) ≥ max_{v∈V (G)} ∏_{i=1}^{N} τ(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?

Cite [? ]

3 Counting Total Number of Leaves

Let G be a graph and T be a spanning tree of G. A leaf of a tree T is a vertex with degree exactly 1 in the tree. Denote by L(T), the set of leaves of T. For ease of notation, we will write T (G) for the set of (labeled) spanning trees of G and will shorten this as 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.

Proposition 3.0.1. If G is a labeled connected simple graph and for v ∈ V (G), then

∑_{T ∈T} |L(T)| = ∑_{v∈V (G)} deg_{G}(v) · |T_{v}|

where T := T (G) and T_{v} := T (G − v).

Proof. Fix v ∈ V (G). Write E_{v} := {e ∈ E(G) : v ∈ e}. There is a bijection between E_{v} × T_{v} and the spanning trees of T which contain v as a leaf. Hence, we use indicators to obtain

∑_{v∈V (G)} deg_{G}(v) · |T_{v}| = ∑_{v∈V (G)} |{T ∈ T : v ∈ L(T)|

= ∑_{v∈V (G)} ∑_{T ∈T} 1_{v∈L(T)} = ∑_{T ∈T} |L(T)|.

We say G is vertex-transitive if for any u, v ∈ V (G) there is an automorphism φ of G such that φ(u) = v and φ(v) = u.

Corollary 3.0.2. If G is vertex-transitive, then

∑_{T ∈T} |L(T)| = n · deg_{G}(v) · |T_{v}|

for any v ∈ V (G).

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).

4 The B-Z Constant: Average Number of Leaves per Vertex

For a graph family indexed by number of vertices, G, where G_{n} represents the n-th graph in the family, we call the following the B-Z constant for G:

lim_{n→∞} \frac{∑_{T ∈T (G_{n})} |L(T)|}{n · τ(G_{n})}

whenever the limit exists. Since the bound \frac{∑ |L(T)|}{nτ(G)} ≤ 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 G is the family of star graphs, its B-Z constant is 1. [Include a brief interpretation/intuition]

Thanks to Corollary 3.0.2, 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 Corollary 3.0.2 in conjunction with Cayley’s Theorem:

Proposition 4.0.1. The B-Z constant for the graph family \{K_{n} : n ≥ 3\} is \frac{1}{e}.

Proof. Recall Cayley’s formula, which states τ(K_{n}) = n^{n−2} for n ≥ 2. With T := T (K_{n}), Corollary 3.0.2 tells us that ∑ |L(T)| = n · (n − 1)^{n−2}. Hence,

\frac{∑ |L(T)|}{n · τ(K_{n})} = (\frac{n − 1}{n})^{n−2} = (1 − \frac{1}{n})^{n−2}

which approaches e^{−1} as n → ∞.

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.

Proposition 4.0.2. For any positive rational number \frac{p}{q} < 1, there is an indexed graph family G which has B-Z constant equal to p/q.

Proof. First, we introduce a graph operation called subdivision. Let e = uv be an edge of G, with u, v ∈ V (G). Let w ∉ V (G). The result of subdividing e in G is the graph G′ where V (G′) := V (G) ∪ {w} and E(G′) := (E(G) \ {e}) ∪ {uw, wv}.

We will construct G by constructing each member G_{k} ∈ G. For each integer k ≥ 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 G is lim_{k→∞} \frac{pk}{qk+1} = \frac{p}{q}.

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 BZc alongside our graph-generating procedures Hnr and Gnr to obtain the results in Section 5.3 and Section 6.3.

5 Powers of a Cycle: Experimental Results

5.1 Generating Functions for the Number of Spanning Trees

In this section, we include our results for the Number of Spanning Trees of the class G_{r}, with 2 ≤ r ≤ 5.

Theorem 5.1.1. The generating function f(t) for the number of spanning trees in G_{2} is

\frac{−36t^{5} + 132t^{4} + 46t^{3} − 353t^{2} − 116t + 125}{(t + 1)^{2}(t^{2} − 3t + 1)^{2}}

Theorem 5.1.2. The generating function f(t) for the number of spanning trees in 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

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.

Theorem 5.1.3. The generating function f(t) for the number of spanning trees in G_{4} is

\frac{N_{4}}{D_{4}}

where N_{4} is a polynomial of degree 53 and

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

Theorem 5.1.4. The generating function f(t) for the number of spanning trees in G_{5} is

\frac{N_{5}}{D_{5}}

where N_{5} is a polynomial of degree 161 and

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}

5.2 Generating functions for the Total Number of Leaves

Theorem 5.2.1. The generating function for the total number of leaves (across all spanning trees of a member) in 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}}.

Theorem 5.2.2. The generating function for the total number of leaves (across all spanning trees of a member) in 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

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.

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 [? ] for detailed results when 4 ≤ r ≤ 5.

Theorem 5.2.3. The generating function for the total number of leaves (across all spanning trees of a member) in G_{4} is

\frac{A_{4}}{B_{4}}

where A_{4} is a polynomial of degree 80 and

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}

5.3 B-Z Constants

See Section 4 to read about our method for computing these constants. Let BZ(G) denote the B-Z constant of a graph family G.

Theorem 5.3.1. The B-Z constant for G_{2} is

−6 + \frac{14\sqrt{5}}{5}.

Theorem 5.3.2. The B-Z constant for G_{3} is

\frac{3}{7} (\frac{45}{2} + 9\sqrt{7} − \frac{1}{2}\sqrt{3857 + 1684\sqrt{7}}) .

Theorem 5.3.3. Let α 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 G_{4} is

\frac{1}{2025} (−216α^{7} − 2144α^{6} + 16344α^{5} + 41056α^{4} − 17064α^{3} − 87936α^{2} − 25304α + 6944) .

Corollary 5.3.4.

BZ(G_{3}) < \frac{117451}{355635} < BZ(G_{4}) < \frac{117452}{355635}

In the previous theorem, α ≈ 0.158778.

6 Powers of a Path: Experimental Results

6.1 Generating functions for the Number of Spanning Trees

In this section, we include our results for the Number of Spanning Trees in the class H_{r}, with 2 ≤ r ≤ 6.

Theorem 6.1.1. The generating function f(t) for the number of spanning trees in H_{2} is

\frac{−3t + 8}{t^{2} − 3t + 1}.

Theorem 6.1.2. The generating function f(t) for the number of spanning trees in H_{3} is

\frac{−16t^{4} + 77t^{3} − 33t^{2} + 39t − 75}{(t − 1)(t^{4} − 4t^{3} − t^{2} − 4t + 1)}.

Theorem 6.1.3. The generating function f(t) for the number of spanning trees in 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

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

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 [? ].

Theorem 6.1.4. The generating function f(t) for the number of spanning trees in H_{5} is

\frac{M_{5}}{E_{5}} .

where M_{5} is a degree 40 polynomial in t and

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)

6.2 Generating functions for the Total Number of Leaves

Theorem 6.2.1. The generating function for the total number of leaves (across all spanning trees of a member) in H_{2} is

\frac{−2(2t^{3} − 15t^{2} + 27t − 9)}{(t^{2} − 3t + 1)^{2}}

Note: the numerator and denominator in the following have the same degree.

Theorem 6.2.2. The generating function for the total number of leaves in H_{3} is

\frac{2(16t^{10} − 154t^{9} + 403t^{8} − 340t^{7} + 963t^{6} − 768t^{5} + 1109t^{4} − 788t^{3} + 509t^{2} − 470t + 96)}{(t − 1)^{2}(t^{4} − 4t^{3} − t^{2} − 4t + 1)^{2}}

Theorem 6.2.3. The generating function for the total number of leaves in 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.

6.3 B-Z Constants

See Section 4 to read about our method for computing these constants. Compare the results in this section to Section 5.3.

Theorem 6.3.1. The B-Z constant for H_{2} is

−6 + \frac{14\sqrt{5}}{5}.

Theorem 6.3.2. The B-Z constant for H_{3} is

\frac{3}{7} (\frac{45}{2} + 9\sqrt{7} − \frac{1}{2}\sqrt{3857 + 1684\sqrt{7}}) .

[The B-Z constants up to H_{5} and G_{5} are actually equal]

7 Verification of Results by Random Sampling

In our implementation, we wrote a procedure to compute the total number of leaves of a graph (NumLeaves or VtxTransNumLeaves) and another to compute the number of spanning trees (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 [? ].

The algorithm we used to sample uniformly random spanning trees is Wilson’s Algorithm, as described in [? ].

8 Accompanying Maple package

In the following procedures, graphs will be represented as an exprseq type in Maple. Particularly, a graph is n,E, where n is a positive integer and E is a set of edges on [n]. We assume all graphs are connected.

Our Maple package broadly depends on the LinearAlgebra library. The RandomTree procedure also makes use of the GraphTheory library. Below we list some key procedures along with their descriptions: NumSpanTree(n,E) given a positive integer n and a set of edges E on the set {1, …, n}, the procedure returns the number of spanning trees of the corresponding graph n, E. NumSpanTreeSeq(F, ArgList, a,b) given the name of a graph-generating procedure F and a list of arguments ArgList, outputs a list of the number of spanning trees for the graphs F(a, op(ArgList)),…,F(b, op(ArgList)). NumLeaves(n,E) given a graph n,E, returns the total number of leaves in such a graph across all its spanning trees. NumLeavesSeq(F, ArgList, a,b) given the name of a graph-generating procedure F and a list of arguments ArgList, outputs a list of the total number of leaves for the graphs F(a, op(ArgList)),…,F(b, op(ArgList)).

VtxTransNumLeavesSeq(F, ArgList, a,b) similar to NumLeavesSeq. However, assumes that the graphs generated

by F are vertex-transitive. Uses Corollary 3.0.2 to compute the output faster. Hnr(n,r) constructs the r-th power of a path on n vertices. Returns n, E. Gnr(n,r) constructs the r-th power of a cycle on n vertices. Returns n, E. BZc(F,Arglist,a,b,k) Using a graph-generating procedure F with fixed arguments ArgList and varying the first argument from a to b, compute the B-Z constant. k adjusts the B-Z computation so that if the index of a graph (in the family) is n, then the graph has k · n vertices. The following procedures generate the outputs for the theorems in this paper: [Add these]

HnrS
GnrS

From Doron Zeilberger’s Cfinite.txt package: [Dr. Z, add more if necessary:] RGF(S,t) given a C-finite sequence S, outputs its rational generating function in the variable t.

9 Questions and Conjectures

[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). Conjecture 9.0.1. The B-Z constants of G_{r} and H_{r} are equal for all r ≥ 1.

Let Δ(G) denote the maximum degree in a graph. G_{n} \ H_{n} [define this appropriately] Conjecture 9.0.2. Let G := {G_{n}}_{n} and H := {H_{n}}_{n} be (indexed) graph families. If H_{n} ⊆ G_{n} for all n, the number of vertices with positive degree in G_{n} \ H_{n} is bounded, and Δ(G_{n} \ H_{n}) is bounded; then, G and H have the same B-Z constant.

[Eugene Zima question about RGF factors]