[Kartik]klblue [Aleyah]adcyan [Laura]lmred [Kelly]kiorange [Ales]akblue

# Edge-Disjoint Spanning Trees on Star-Product Networks

Aleyah Dawkins  George Mason UniversityFairfaxVirginiaUSA<EMAIL_ADDRESS>,
Kelly Isham  Colgate UniversityHamiltonNew YorkUSA<EMAIL_ADDRESS>,  Ales
Kubicek  ETH ZürichZurichSwitzerland<EMAIL_ADDRESS>,  Kartik
Lakhotia  Intel LabsSanta ClaraCaliforniaUSA<EMAIL_ADDRESS>and
Laura Monroe  Los Alamos National LaboratoryLos AlamosNew MexicoUSA
<EMAIL_ADDRESS>
(2024)

###### Abstract.

Star-product graphs are a natural extension of the Cartesian product, but have
not been well-studied. We show that many important established and emerging
network topologies, including HyperX, SlimFly, BundleFly, PolarStar, mesh, and
torus, are in fact star-product graphs. While this connection was known for
BundleFly and PolarStar, it was not for the others listed.

We extend a method of constructing maximal and near-maximal sets of edge-
disjoint spanning trees on Cartesian products to the star product, thus obtain
maximal or near-maximal sets of edge-disjoint spanning trees on new networks
of importance, where such sets can improve bandwidth of collective operations
and therefore accelerate many important workloads in high-performance
computing.

In-network Collectives, Allreduce, Star Product, Spanning Trees, Hamiltonian
Paths, PolarStar, Slimfly, HyperX, Bundlefly

This work was supported in part by the U.S. Department of Energy through the
Los Alamos National Laboratory, operated by Triad National Security, LLC, for
the National Nuclear Security Administration of U.S. Department of Energy
(Contract No. 89233218CNA000001), and by the U.S. DOE LDRD program at Los
Alamos National Laboratory under project number 20230692ER. The U.S.
Government retains an irrevocable, nonexclusive, royalty-free license to
publish, translate, reproduce, use, or dispose of the published form of the
work and to authorize others to do the same. This paper has been assigned the
LANL identification number LA-UR-24-20699.

††copyright: acmcopyright††journalyear: 2024††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Networks Data center networks††ccs:
Networks Network design principles††ccs: Mathematics of computing Network
flows††ccs: Mathematics of computing Trees††ccs: Mathematics of computing
Combinatoric problems

##  1\. Introduction and Background

###  1.1. Motivation

A network topology can be modeled as a graph connecting the network switches
with compute endpoints associated with the switches. In this paper, we focus
on the graph between the switches.

A set of spanning trees in a graph $G$ is _edge-disjoint_ if no two contain a
common edge. Finding a set of edge-disjoint spanning trees (EDSTs) in this
graph closely relates to the performance of collective operations such as
Allreduce (Lakhotia et al., 2023a; Zhao et al., 2023) and fault tolerant
communication (Fragopoulou and Akl, 1996) in large distributed memory systems.
It is of great interest to construct maximal or near-maximal set of EDSTs to
maximize collective bandwidth and improve fault-tolerance of large systems
(Lakhotia et al., 2023a; Ku et al., 2003).

By improving collective bandwidth using large set of EDSTs, we can effectively
enhance the performance of crucial high-performance computing and machine
learning workloads, such as large language training models (Sergeev and Del
Balso, 2018; Akiba et al., 2017; Patwary et al., 2019; Narayanan et al.,
2021). Thus, the existence of a maximal set of EDSTs is an advantage for any
such network, as shown for the PolarFly network in (Lakhotia et al., 2023a).

###  1.2. Prior Work

There are recent comprehensive surveys on the existence and construction of
EDSTs on general graphs and networks (Palmer, 2001a; Cheng et al., 2023).
There are several ways to obtain a maximal or near-maximal set of EDSTs for
specific network topologies. Roskind and Tarjan introduced an algorithm that
is able to find $k$ EDSTs for an arbitrary network in $O(n^{2}k^{2})$ (Roskind
and Tarjan, 1985; Roskind, 1983). Another option is to derive an algorithm or
a construction based on topological properties of the specific underlying
network. Prior works show such constructions on certain networks such as
Hypercube and PolarFly (Fragopoulou and Akl, 1996; Barden et al., 1999;
Lakhotia et al., 2023a). The network construction mechanism, such as a graph
product, is also an important topological property and has been previously
used to construct maximal or near-maximal set of EDSTs in Cartesian product
graphs (Ku et al., 2003).

In this work, we generalize this result and introduce our own construction of
a maximal or near-maximal set of EDSTs in star-product networks. Many novel
network topologies such as Slim Fly, Bundlefly and PolarStar are constructed
using the star product (Ahn et al., 2009; Besta and Hoefler, 2014; Lei et al.,
2020; Lakhotia et al., 2023b), which is a generalization of the Cartesian
product. These star-product topologies have several desirable characteristics
for networking, such as scalability and fiber bundling (Lakhotia et al.,
2023b; Lei et al., 2020). This motivates the need to characterize other
benefits of these topologies and our work is an effort in that direction.

###  1.3. Contributions

Contributions of this paper include:

  * •

General construction of a maximal or near-maximal sets of EDSTs for star
products. This generalizes a Cartesian result and applies to any star product
graph or network.

  * •

Characterization of EDSTs in star-product network topologies. We show that for
many emerging topologies, such as Slim Fly, BundleFly and PolarStar, our
construction produces the maximal number of EDSTs.

  * •

Discussion of the star product as an important construction for scalable low-
diameter high-performance networks. Such networks include not only known
Cartesian product networks, such as HyperX, but also an emerging generation of
mathematically based star-product networks.

  * •

Implications of viewing the star product network as a generalization of a
Cartesian network. This points to the possibility of generalizing the many
known facts about Cartesian networks to the benefit of known star-product
networks, such as the maximal sets of EDSTs on star products we discuss here.

##  2\. The Star Product

We discuss the star product as a generalization of the familiar Cartesian
product in this section. We begin by discussing the Cartesian product, then
show how the star product generalizes this. Throughout this paper,
$G=(V(G),E(G))$ is a graph with vertex set $V(G)$ and edge set $E(G)$.

###  2.1. The Cartesian Product

###### Definition 2.1.1.

[Cartesian product] A _Cartesian product_ of two graphs $G_{s}$ and $G_{n}$ is
a graph product where vertices are $(a,b)$ with $a\in G_{s}$ and $b\in G_{n}$,
and edges are such that either $a_{1}=b_{1}$ and $(a_{2},b_{2})$ is an edge in
$G_{n}$, or $a_{2}=b_{2}$ and $(a_{1},b_{1})$ is an edge in $G_{s}$.

One may picture a Cartesian product as in Figure 1(a):

  * •

The large-scale form of the Cartesian product is that of a factor graph
(called here the _structure graph_).

  * •

Copies of the other graph (the _supernode_) are put in place of each of the
vertices of the structure graph.

  * •

Edges of the structure graph are expanded by joining corresponding vertices
from neighboring supernodes.

Cartesian product networks are very well studied and there is a large body of
knowledge concerning them, including such things as bisection bandwidth (Aroca
and Anta, 2014), path diversity and fault diameter (Day and Al-Ayyoub, 2000),
routing algorithms (Youssef, 1991), deadlock avoidance (KráĽovič et al.,
1998), and resource placement (Imani et al., 2010). This motivates the study
of star product networks as a generalization of Cartesian product networks.
Since several emerging networks are based on a star-product graph
construction, we aim to generalize the wealth of knowledge about Cartesian
products to star products, in the context of networking.

###  2.2. Intuition for the Star Product

Intuitively, the star product has the large-scale form of its structure graph,
as in the Cartesian product. However, in the star product, the Cartesian-
product requirement that edges join corresponding supernode vertices is
loosened. Instead, the vertex connections between neighboring supernodes may
be defined by any convenient bijection. This is illustrated in Figure 1(b).

(a) Cartesian Product

(b) Star Product

Figure 1. A comparison of a Cartesian and star products. Each has structure
graph $C_{4}$, the cycle on $4$ vertices, and supernode $L_{2}$, the path on
$2$ vertices. However, in the star product, the top structure graph bijection
between supernodes does not send corresponding supernode vertices to each
other. This is only one of many possible star products on $C_{4}$ and $L_{2}$.

Note that the bijections need not be the same for all neighboring supernodes,
but may be defined differently for each neighboring supernode pair, giving
even more flexibility for connectivity.

Intuitively, this gives a graph that in the large scale looks like the
structure graph, with supernodes as (large-scale) vertices, and having
“twisted edges” connecting supernodes. These edges follow structure graph
edges, and are such that each vertex in a supernode is connected to exactly
one vertex in a neighboring supernode.

The Cartesian product is clearly a special case of this construction,. The
edges are not “twisted”, instead each vertex in a supernode is sent to the
same vertex in other supernodes. The Cartesian product is commutative:
switching the order of the factor graphs gives an isomorphic graph. The star
product may not be not commutative, and very often, one star product ordering
is greatly preferable to the other for networking purposes.

###  2.3. Formal Definition of the Star Product

The star product was introduced and defined formally by Bermond, Farhi and
Delorme in (Bermond et al., 1982), as below.

Since the connections between supernode vertices are not the simple edges
between corresponding vertices seen in the Cartesian product, one must
explicitly define connections between supernodes. Intuitively, $f_{e_{s}}$ in
the definition below is exactly this rule for joining vertices between two
neighboring supernodes $A_{x}$ and $A_{y}$ corresponding to neighboring
structure-graph vertices $x$ and $y$.

###### Definition 2.3.1.

(Bermond et al., 1982) [Star Product] Let $G_{s}=(V_{s},E_{s})$ and
$G_{n}=(V_{n},E_{n})$ be graphs. For each ordered edge $e_{s}=(x,x^{\prime})$
in $G_{s}$, define a bijection $f_{e_{s}}$ on the vertices of $G_{n}$. A _star
product_ $G^{*}=G_{s}*G_{n}$ is a graph product where (i) the vertices are all
$(x,y)$ such that $x\in V_{s}$ and $y\in V_{n}$, and (ii) a pair $(x,y)$ and
$(x^{\prime},y^{\prime})$ of vertices in $G^{*}$ is joined by an edge when
either

  1. (1)

$x=x^{\prime}$ and $(y,y^{\prime})$ is an edge in $G_{n}$, or

  2. (2)

$e_{s}=(x,x^{\prime})$ is an edge in $G_{s}$ and $y^{\prime}=f_{e_{s}}(y)$.

$G_{s}$ is called the _structure graph_ and $G_{n}$ is called the _supernode
graph_.

Since neighboring supernodes are bijectively connected, the bijection $f$
defining edges from $A_{x}$ to $A_{x^{\prime}}$ fully determines the bijection
defining edges from $A_{x^{\prime}}$ to $A_{x}$, which is then $f^{-1}$.

The following properties are useful in analyzing a star product.

######  Theorem 2.3.2.

Let $G^{*}=G_{s}*G_{n}$ be a star product. Then

  1. (1)

(Bermond et al., 1982) The number of vertices is $\lvert V(G^{*})\rvert=\lvert
V_{s}\rvert\lvert V_{n}\rvert$.

  2. (2)

(Bermond et al., 1982) If the maximum degrees in $G_{s}$ and $G_{n}$ are
$d_{s}$ and $d_{n}$, respectively, the maximum degree of $G^{*}$ is $d\leq
d_{s}+d_{n}$.

  3. (3)

(Bermond et al., 1982) If the diameters of $G_{s}$ and $G_{n}$ are $D_{s}$ and
$D_{n}$, respectively, then the diameter of $G^{*}$ is given by $D\leq
D_{s}+D_{n}$.

  4. (4)

When there are no self-loops in the $G_{s}$, the number of edges is $\lvert
E(G^{*})\rvert=\lvert V_{s}\rvert\lvert E_{n}\rvert+\lvert V_{n}\rvert\lvert
E_{s}\rvert$.

###  2.4. Examples of Star Product Networks

The star product has been explicitly used in the construction of only two
networks, Bundlefly (Lei et al., 2020) and PolarStar (Lakhotia et al., 2023b).
However, we see here that several other emerging networks are actually star
products as well. Thus, general theorems about star products may be of use
across several different networks of current interest.

###### Example 2.4.1.

[Cartesian product / Mesh, Torus, HyperX (Ahn et al., 2009)] All of these
networks are Cartesian products, and as such, each vertex in a supernode is
joined by an edge to its corresponding vertex in each of the other supernodes.

  * •

In a mesh network, the supernode is an $n$-dimensional Euclidean space and the
structure graph is a $2$-path.

  * •

In a torus, the structure graph is an $n-1$-dimensional torus and the
supernode is a circle graph.

  * •

In a regular $(2,S,0,0)$ HyperX network, both the structure and supernode
graphs are the complete graph on $S$ vertices, and each vertex in a supernode
is joined by an edge to its corresponding vertex in each of the other
supernodes.

  * •

In a regular $(L,S,0,0)$ HyperX, the structure graph is the complete graph on
$S$ vertices and the supernode is the regular $(L-1,S,0,0)$ HyperX graph.

  * •

In an $(L,\\{S_{1},...S_{L}\\},0,0)$ HyperX, the structure graph is the
complete graph on $S_{L}$ vertices, and the supernode is the
$(L-1,\\{S_{1},...S_{L-1}\\},0,0)$ HyperX graph.

###### Example 2.4.2.

[McKay-Miller-Širáň graph (McKay et al., 1998) / Slim Fly (Besta and Hoefler,
2014)] The structure graph in the _McKay-Miller-Širáň ( $H_{q}$) graph_ is the
complete bipartite graph $K_{q,q}$ on $2q$ vertices, where $q$ is a prime
power. Connections internal to supernodes and the bijective $\rho$ connections
between supernodes are defined via constructs from Galois theory, given by
certain Cayley graphs $C(q)$, see (McKay et al., 1998; Besta and Hoefler,
2014) for details. $H_{q}$ was used for the _Slim Fly_ network, giving a
diameter-$2$ network of high order and having many other desirable
characteristics.

###### Example 2.4.3.

[$P$ star-product graph (Bermond et al., 1982) / Bundlefly (Lei et al., 2020)]
The _$P$ star product_ was defined in the same paper as the original star
product. The authors give properties $P$ giving better constraints on diameter
than the generic star product, and give examples.

The _Bundlefly_ network construction is based on the $P$ star product, using
the MMS graph as the structure graph and the technical $P_{1}/P^{*}$
constructions, with an associated set of $f$ bijections, as the supernodes.
Bundlefly does not use the best possible structure graph; however, it was the
first network topology to our knowledge to explicitly name the star product as
its construction.

###### Example 2.4.4.

[$R$ star-product graph (Lakhotia et al., 2023b) / PolarStar (Lakhotia et al.,
2023b)] The _$R$ star product_ (Lakhotia et al., 2023b) is similar to the $P$
star product, but may be used to construct supernodes larger than any known
$P$ supernode, and thus larger graphs than any known $P$ star product. Details
of this construction are in (Lakhotia et al., 2023b).

The _PolarStar_ network construction is an $R$ star product, using the best
known structure graph, the Erdős-Rényi polarity graph ($ER_{q}$) (Erdős and
Rényi, 1962; Brown, 1966), and a large $R^{*}$ graph as the supernode. For
their radixes, the $ER_{q}$ graphs asymptotically approach the Moore bound for
graph order very quickly, so when combined with the large $R^{*}$ graph in a
star product, the graph is of higher order than any previously known for
larger radixes.

###  2.5. Star Product Advantages for Network Design

The star product is very useful for network design. It shares many advantages
of the Cartesian product, with an additional advantage of constrained
diameter, when carefully constructed.

  * •

Large networks with small diameter may be created using the star product.

    * –

Constrained diameter. Given a proper choice of bijections, the diameter of the
star product $G^{*}$ is no more than $D_{s}+1$. This choice is discussed in
(Bermond et al., 1982) and (Lakhotia et al., 2023b).

    * –

Large graphs. By Theorem 2.3.2(1), the number of nodes is just the product of
the number of nodes in each of the factor graphs, so if large factor graphs
are chosen, the resulting star product is also large.

    * –

Both Bundlefly (Lei et al., 2020) and PolarStar (Lakhotia et al., 2023b) are
diameter-$3$ networks of large order that use such constructions.

  * •

Modular structure for ease of deployment.

    * –

Every supernode has the same internal structure that can be mapped to racks or
cabinets.

    * –

There are a large number of links between every adjacent pair of supernodes
that can be bundled using multi-core fibers to reduce cabling cost and
complexity (Lei et al., 2020; Lakhotia et al., 2023b).

  * •

Flexibility in network design, since edges between supernodes are defined on a
supernode-pair basis.

  * •

Much exploitable mathematical structure, which is then applied to the network,
for routing or other uses (Besta and Hoefler, 2014; Lei et al., 2020; Lakhotia
et al., 2023b), e.g., the construction of EDSTs discussed here. This includes
potentially exploitable similarity to Cartesian product networks.

In the rest of this paper, we will show that star product networks support
constructing large, and even maximal, sets of EDSTs within them, generalizing
a similar result on Cartesian products. Our constructions are valid for any
star product, so in particular are valid for all networks mentioned in Section
2.4.

##  3\. Number of EDSTs in Star Products

Conditions | EDSTs | Maximum? | Ths. from (Ku et al., 2003)
---|---|---|---
|  $r_{1}=t_{1}$ AND $r_{2}=t_{2}$
---
$t_{1}+t_{2}$ | Yes | Ths. 1 and 2
|  $r_{1}\geq t_{1}$ AND $r_{2}\geq t_{2}$
---
$t_{1}+t_{2}$ | Maybe |  stated in (Ku et al., 2003)
$r_{1}=0$ AND $r_{2}=0$ | $t_{1}+t_{2}-1$ | Yes |  Cors. $1$ and $2$
any Cartesian product | $t_{1}+t_{2}-1$ | Maybe | Th. 3
Table 1. The number of spanning trees that may be generated on Cartesian products, given conditions on $t_{i}$, the number of EDSTs of factor $G_{i}$, and $r_{i}$, the number of remaining edges in factor $G_{i}$, as shown in (Ku et al., 2003). In fact, maximality in rows $1$ and $3$ can be proven for a range of $r_{1}$ and $r_{2}$ by following the proofs of these theorems and corollaries. Conditions | EDSTs | Maximum? | Theorem
---|---|---|---
|  $r_{1}=t_{1}$ AND $r_{2}=t_{2}$
---
$t_{1}+t_{2}$ | Yes | 4.5.2
|  $r_{1}\geq t_{1}$ AND $r_{2}\geq t_{2}$
---
$t_{1}+t_{2}$ | Maybe | 4.5.1
|  $r_{1}\geq t_{1}$ OR $r_{2}\geq t_{2}$
---
$t_{1}+t_{2}-1$ | Maybe | 4.5.9
|  $r_{1}=0$ AND $r_{2}=0$
---
AND Property 4.6.1
$t_{1}+t_{2}-1$ | Yes | 4.6.2
|  Property 4.6.1
---
$t_{1}+t_{2}-1$ | Maybe | 4.6.2
any star product | $t_{1}+t_{2}-2$ | Maybe | 4.3.1
Table 2. The number of spanning trees we have generated on star products,
given conditions on $t_{i}$, the number of EDSTs of factor $G_{i}$, and
$r_{i}$, the number of remaining edges in factor $G_{i}$. In fact, maximality
in rows $1$ and $4$ can be proven for a range of $r_{1}$ and $r_{2}$ by
following proofs of these theorems.

In this section, we cite results on EDSTs in Cartesian products, discuss our
analogous results for star products, and find maximal or near-maximal sets of
EDSTs for star products. Thus, the problem of finding maximal sets of EDSTs in
star products reduces to that of finding them in their factor graphs.

We start with a comparison. Table 1 shows the number of EDSTs constructed for
Cartesian products in (Ku et al., 2003) and Table 2 shows the number of EDSTs
constructed for star products in this paper. The theorems from Table 2 are
stated and proved in Section 4, and constructions are provided.

The Cartesian case Theorems $1$ and $2$ from (Ku et al., 2003) generalize, as
may be observed in Tables 1 and 2. The Cartesian Theorem $3$ from (Ku et al.,
2003) generalizes under the right conditions. Fortunately, these conditions
hold in most cases of interest in this paper. Finally, our Theorem 4.3.1 gives
a generic construction for EDSTs on star products with no conditions, with one
fewer tree than is shown in the Cartesian case in Theorem $1$ from (Ku et al.,
2003).

We note that the EDSTs for the star product must be chosen much more carefully
than those in the Cartesian case.

All networks from Section 2.4 are covered by Theorems 4.5.1, 4.5.2 and 4.5.9.
In Table 3, we compare results obtained by these theorems to the maximum
possible EDSTs in these star-product networks, and show that most of the time,
we do indeed achieve the maximum number of spanning trees by using these
theorems. The theoretical maximums in this table are derived combinatorially
from the number of vertices and edges in each graph.

The derivations for the factor graphs are shown in the Appendix at the end of
the paper. It is not necessary to read the appendix to understand the paper,
but the calculations there show correctness of the parameters asserted in the
tables.

Network | Parameters | $t_{s}$ | $r_{s}$ | $t_{n}$ | $r_{n}$ | Th. # |  | Constructed
---
EDSTs
| Bound on
---
EDSTs
Maximum? | Radix
| $q=4k+1$ | $2k$ | $6k+1$ | $k$ | $k$ | 4.5.1 | $3k$ | $3k$ | Yes | $6k+1$
| $q=4k$ | $2k$ | $2k$ | $k$ | $k$ | 4.5.2 | $3k$ | $3k$ | Yes * | $6k$
Slim Fly / $H_{q}$ $K_{q,q}$*C($q$) | $q=4k-1$ | $2k-1$ | $6k-2$ | $k$ | $k$ | 4.5.1 | $3k-1$ | $3k-1$ | Yes | $6k-1$
|  | $q=4\ell+1$
---
$a=4k+1$
$3\ell$ | $q^{2}+3\ell$ | $k$ | $k$ | 4.5.1 | $3\ell+k$ | $3\ell+k$ | Yes | $6\ell+1+2k$
|  | $q=4\ell$
---
$a=4k+1$
$3\ell$ | $3\ell$ | $k$ | $k$ | 4.5.2 | $3\ell+k$ | $3\ell+k$ | Yes * | $6\ell+2k$
Bundlefly $H_{q}$*QR($a$) |  | $q=4\ell-1$
---
$a=4\ell+1$
$3\ell-1$ | $q^{2}+3\ell-1$ | $k$ | $k$ | 4.5.1 | $3\ell+k-1$ | $3\ell+k-1$ | Yes | $6\ell-1+2k$
|  |  $q$ even
---
$a=4k+1$
$\frac{q}{2}$ | $\frac{q(q+1)}{2}$ | $k$ | $k$ | 4.5.1 | $\left\lfloor\frac{q}{2}\right\rfloor+k$ | $\left\lfloor\frac{q}{2}\right\rfloor+k$ | Yes | $q+1+2k$
PolarStar $ER_{q}$*QR($a$) |  |  $q$ odd
---
$a=4k+1$
$\frac{q+1}{2}$ | $0$ | $k$ | $k$ | 4.5.9 | $\left\lfloor\frac{q}{2}\right\rfloor+k$ | $\left\lfloor\frac{q}{2}\right\rfloor+k$ | Yes | $q+1+2k$
|  |  $q$ even
---
$d=4m$
$\frac{q}{2}$ | $\frac{q(q+1)}{2}$ | $\frac{d}{2}$ | $\frac{d}{2}$ | 4.5.1 | $\left\lfloor\frac{q+d}{2}\right\rfloor$ | $\left\lfloor\frac{q+d}{2}\right\rfloor$ | Yes | $q+1+d$
|  |  $q$ even
---
$d=4m+3$
$\frac{q}{2}$ | $\frac{q(q+1)}{2}$ | $\frac{d-1}{2}$ | $\frac{3d+1}{2}$ | 4.5.1 | $\left\lfloor\frac{q+d}{2}\right\rfloor$ | $\left\lfloor\frac{q+d}{2}\right\rfloor$ | Yes | $q+1+d$
|  |  $q$ odd
---
$d=4m$
$\frac{q+1}{2}$ | $0$ | $\frac{d}{2}$ | $\frac{d}{2}$ | 4.5.9 | $\left\lfloor\frac{q+d}{2}\right\rfloor$ | $\left\lfloor\frac{q+d}{2}\right\rfloor$ | Yes | $q+1+d$
PolarStar $ER_{q}$*IQ($d$) |  |  $q$ odd
---
$d=4m+3$
$\frac{q+1}{2}$ | $0$ | $\frac{d-1}{2}$ | $\frac{3d+1}{2}$ | 4.5.9 | $\left\lfloor\frac{q+d}{2}\right\rfloor-1$ | $\left\lfloor\frac{q+d}{2}\right\rfloor$ | Maybe | $q+1+d$
|  |  |  |  |  |  |  |  |  |
Table 3. This table gives parameters and statistics on important star product
graphs, using factor graph $t$ and $r$ values shown in Table 4. It counts the
number of edge-disjoint spanning trees that are constructed via the theorems
shown in Table 2, and compares this to the upper bound on edge-disjoint
spanning trees calculated directly from the number of vertices and edges of
the graph. If Theorem 4.5.2 applies, or if the constructed number meets the
upper bound, we know that the calculated number is indeed maximal. We mark the
Theorem 4.5.2 cases with *. Note that this chart assumes that all factor
graphs have sets of EDSTs that reach their theoretical maximum. We know this
for Paley (denoted as $QR(a)$, or alternately as $C(a)$ when $a=4k+1$)
(Alspach et al., 2012), bipartite $K_{q,q}$ (Palmer, 2001b), complete $K_{m}$
(Palmer, 2001b), and $ER_{q}$ (Lakhotia et al., 2023a).

##  4\. Constructing Star-Product EDSTs

In this section, we prove the theorems on finding large sets of EDSTs in star
products shown in Table 2. Our results are completely general to any graph
formed by a star product, so in particular hold for all networks listed in
Section 2.4.

Recall that a star product graph is formed by applying a product operation on
two factor graphs - _supernode_ and _structure_ graphs. As per the definition
of star product, each vertex in the structure graph is replaced with a unique
instance of the supernode graph. Further, each edge in the structure graph
translates to a set of disjoint edges between a pair of supernodes in the
product graph. Hence, for each spanning tree in the structure graph, there are
multiple disjoint instances of it in the product graph. We combine instances
of the spanning trees inside supernodes with the trees in the structure graph
to create spanning trees for the star product.

  * •

Our Universal solution (Section 4.3) uses straightforward methods to connect
factor graphs’ spanning trees and does not require any conditions on the
factor graphs,

  * •

Our Maximal solution (Section 4.4) carefully selects the edges from the
spanning trees of factor graphs. Note that this solution uses additional edges
in factor graphs that are not in the individual spanning trees, to construct
extra trees and reach the maximal number of EDSTs.

It is important to note that the constructions described in this paper work
even when the set of spanning trees in the factor graphs is not maximal. The
only reason we need a maximal number of spanning trees in the factor graphs is
to guarantee maximality in the product.

###  4.1. Why is Maximality important?

Our universal solution gives $2$ less EDSTs than the maximal solution. While
this may seem like a small loss, it can compound when the factor graphs are
also star products. For instance, in Bundlefly (Lei et al., 2020), one of the
factor graphs is McKay-Miller-Siran ($H_{q}$) graph which is a star product.
Applying universal solution on both $H_{q}$ and Bundlefly gives $4$ less trees
than the maximal. For a radix $32$ network, this is $25\%$ less than the
maximal. The losses can be even higher if both factor graphs are star
products.

###  4.2. Preliminary Facts for the Constructions

We consider a star product $G^{*}=G_{s}*G_{n}$ of simple connected graphs
$G_{s}=(V_{s},E_{s})$ and $G_{n}=(V_{n},E_{n})$, and assume we have a maximal
set of EDSTs for $G_{s}$ and $G_{n}$, namely
$\mathbf{X}=\\{X_{1},X_{2},\ldots,X_{t_{1}}\\}$ and
$\mathbf{Y}=\\{Y_{1},Y_{2},\ldots,Y_{t_{2}}\\}$. The edges left in $G_{s}$ and
$G_{n}$ after removing all subgraphs $X$ and $Y$, respectively, are called
_non-tree_ edges, and subgraphs induced by non-tree edges are denoted as
$N_{s}$ and $N_{n}$, respectively.

For construction purposes, we consider a directed version of $X_{1}$, denoted
as $\bar{X}_{1}$, that is rooted at a vertex $o\in V_{s}$ and has directed
edges such that each edge goes from a parent to a child, where parent is the
vertex closer to the root $o$ than the child. Thus, for any edge, the child
becomes the sink and for any given $x^{\prime}\in V_{s}$, there is at most one
edge $(x,x^{\prime})\in\bar{X}_{1}$ such that $x^{\prime}$ is a sink of this
edge. The directions are only used to select disjoint edges across the same
pair of adjacent supernodes by enforcing different sinks (as shown in
Construction 4.3.3). In the final EDSTs, all edges are undirected.

The list below gives all the notations used in our constructions:

  * •

$\mathbf{X}$, a set of maximal EDSTs in $G_{s}$ of size $t_{1}$

  * •

$\mathbf{Y}$, a set of maximal EDSTs in $G_{n}$ of size $t_{2}$

  * •

$N_{s}$, the subgraph of $G_{s}$ formed by the non-tree edges

  * •

$N_{n}$, the subgraph of $G_{n}$ formed by the non-tree edges

  * •

$r_{1}$, the number of edges in $N_{s}$

  * •

$r_{2}$, the number of edges in $N_{n}$

  * •

$U_{s}$, a set of $t_{1}$ vertices in $N_{s}$ such that for each $u\in U_{s}$,
there is a path in $N_{s}$ from $u$ to some $u^{\prime}\in V_{s}\setminus
U_{s}$

  * •

$U_{n}$, a set of $t_{2}$ vertices in $N_{n}$ such that for each $v\in U_{n}$,
there is a path in $N_{n}$ from $v$ to some $v^{\prime}\in V_{n}\setminus
U_{n}$

  * •

$o$, a vertex in $U_{s}$

  * •

$\bar{X}_{1}$, directed version of $X_{1}$ rooted at $o$

  * •

$o^{\prime}$, a vertex in $U_{n}$

###  4.3. A Universal Solution of EDSTs

We show in this section an intuitive and universal set of EDSTs on any star
product with no conditions.

######  Theorem 4.3.1.

The star product $G^{*}$ has $t_{1}+t_{2}-2$ EDSTs with no conditions on
$G_{s}$ and $G_{n}$. This may or may not be the maximum number possible.

To prove Theorem 4.3.1, we describe two constructions that produce a large set
of EDSTs. Then we show that these two sets of trees are edge-disjoint.

######  Construction 4.3.2.

Construct spanning trees $T_{i|2\leq i\leq t_{1}}$. Construction of $T_{i}$ is
via $X_{i}$ and $Y_{1}$ for all $2\leq i\leq t_{1}$. For each $2\leq i\leq
t_{1}$, choose a unique $u_{i}\in V_{s}$ such that $u_{i}=u_{j}$ iff $i=j$.

Intuitive Construction: For tree $T_{i}$, we connect vertices within a
supernode $u_{i}$ using $Y_{1}$ (given by the edges in (1)), and connect the
supernodes using all instances of $X_{i}$ in $G^{*}$. We depict this in Figure
2 under Construction 4.5.3 with one difference that here, we allow the
supernodes $u_{i}$ to be arbitrary elements in $V_{s}$.

In $G^{*}$, each edge $(x,x^{\prime})\in E_{s}$ becomes a set of $\lvert
V_{n}\rvert$ independent edges connecting vertices in supernode $x$ with
vertices in supernode $x^{\prime}$ bijectively. Therefore, the edges in (2)
formed from $X_{i}$ give $\lvert V_{n}\rvert$ disjoint trees in $G^{*}$, which
form a disconnected spanning forest in $G^{*}$. Constructing a $Y_{1}$ in
supernode $u_{i}$ connects all trees in the forest, resulting in a single
connected component which is a spanning tree for $G^{*}$. The uniqueness of
$X_{i}$ and $u_{i}$ for each $2\leq i\leq t_{1}$ ensures that the spanning
trees are edge-disjoint.

Mathematical Construction: Formally, we construct the spanning tree $T_{i}$
from the union of the following edge sets:

(1) $\displaystyle\\{\left((u_{i},y),(u_{i},y^{\prime})\right)\ |\
(y,y^{\prime})\in E(Y_{1})\\}$ (2)
$\displaystyle\\{((x,h),(x^{\prime},f_{(x,x^{\prime})}(h)))\ |\
(x,x^{\prime})\in E(X_{i}),h\in V_{n}\\},$

where $2\leq i\leq t_{1}$, $u_{i}\in V_{s}$ and $u_{i}=u_{j}$ if and only if
$i=j$.

######  Construction 4.3.3.

Construct spanning trees $T_{i|2\leq i\leq t_{2}}^{\prime}$. Construction of
$T_{i}^{\prime}$ via $Y_{i}$ and $X_{1}$ for all $2\leq i\leq t_{2}$. For each
$2\leq i\leq t_{2}$, choose a unique $v_{i}\in V_{n}$ such that $v_{i}=v_{j}$
iff $i=j$.

Intuitive Construction: For tree $T_{i}^{\prime}$, we connect vertices within
all supernodes using $Y_{i}$, and connect the supernodes using edges
corresponding to $X_{1}$. We depict this in Figure 2, Construction 4.5.4, with
a difference that here, the $v_{i}$ may be an arbitrary vertex in $V_{n}$.

Since $Y_{i}$ is a spanning tree in $G_{n}$, constructing $Y_{i}$ in each
supernode connects all vertices within each supernode (given by the edges in
(4)). For inter-supernode connectivity, we carefully pick the edges in
$G^{*}$. For any edge $(x,x^{\prime})\in\bar{X}_{1}$ with $x^{\prime}$ as the
sink, we select an edge between supernodes $x$ and $x^{\prime}$ such that the
incident vertex in sink supernode $x^{\prime}$ is the particular vertex
$v_{i}\in V_{n}$. Since $\bar{X}_{1}$ is spanning in $G_{s}$, these edges
connect all supernodes, and with $Y_{i}$ instances in each supernode, form a
single connected component that is a spanning tree in $G^{*}$. By selecting
unique $v_{i}$ and $Y_{i}$ for each $2\leq i\leq t_{2}$, we maintain edge-
disjointness of all spanning trees.

Mathematical Construction: Formally, we construct the spanning tree
$T_{i}^{\prime}$ from the union of the following edge sets:

(3) $\displaystyle\\{((x,f_{(x,x^{\prime})}^{-1}(v_{i})),(x^{\prime},v_{i}))\
|\ (x,x^{\prime})\in\bar{X}_{1}\\}\ \text{and}$ (4)
$\displaystyle\\{((g,y),(g,y^{\prime}))\ |\ g\in V_{s},(y,y^{\prime})\in
E(Y_{i})\\},$

where $2\leq i\leq t_{2}$, $v_{i}\in V_{n}$ and $v_{i}=v_{j}$ if and only if
$i=j$.

###### Proof of Theorem 4.3.1.

First, we show that Construction 4.3.2 produces $t_{1}-1$ spanning trees in
$G^{*}$. Consider the subgraph $T_{i}$ with $Y_{1}$ in supernode $u_{i}$,
which we refer to as the _root supernode_. Since $|V_{s}|\geq t_{1}$, we can
always find a unique supernode $u_{i}$ for $T_{i}$. It is clear that $T_{i}$
spans all vertices in the root supernode using edges from (1). Now consider
level $1$ supernodes i.e. the supernodes corresponding to neighbors of $u_{i}$
in $X_{i}$. The edges in (2) cover all vertices in the level 1 supernodes
since $f_{(x=u_{i},x^{\prime})}$ is a bijection for all
$(x=u_{i},x^{\prime})\in E_{s}$. Since there are no edges within the level $1$
supernodes, it is clear that the subgraph of $T_{i}$ induced by $u_{i}$ and
level $1$ supernodes is connected and acyclic. Continuing by induction on
subsequent levels of $X_{i}$, $T_{i}$ is a spanning tree in $G^{*}$.

Next, we show that Construction 4.3.3 produces $t_{2}-1$ spanning trees in
$G^{*}$. Consider the subgraph $T_{i}^{\prime}$ and the root $o$ of
$\bar{X}_{1}$ as defined in Section 4.2. We construct $Y_{i}$ within supernode
$o$, which connects all vertices in supernode $o$ and is acyclic. Now consider
the supernodes corresponding to level $1$ nodes in $\bar{X}_{1}$ i.e. the
supernodes adjacent to root supernode $o$. Clearly, level $1$ supernodes are
connected to $o$ via a single edge in $G^{*}$ (see (3)) and are internally
connected by $Y_{i}$. Note that there is no edge between a pair of level $1$
supernodes because $X_{1}$ is a tree. Hence, the subgraph of $T_{i}^{\prime}$
induced by supernode $o$ and level $1$ supernodes is connected and acyclic.
Continuing inductively on the levels of $\bar{X}_{1}$ proves that
$T_{i}^{\prime}$ is a spanning tree in $G^{*}$.

Finally, we show that all $t_{1}+t_{2}-2$ spanning trees are edge-disjoint.
Clearly, edges corresponding to $Y_{i}$ for all $2\leq i\leq t_{2}$ and
$X_{i}$ for all $2\leq i\leq t_{2}$ are used in at most one spanning tree.
$Y_{1}$ is used in all trees $T_{i|2\leq i\leq t_{1}}$ but is constructed in
disjoint supernodes for all the trees. Hence, $Y_{1}$ edges do not overlap
across the trees. Edges corresponding to $X_{1}$ are used in all trees
$T_{i|2\leq i\leq t_{2}}^{\prime}$. Consider any edge
$e=((x,y),(x^{\prime},f_{(x,x^{\prime})}(y)))$ in $G^{*}$ such that
$(x,x^{\prime})\in X_{1}$. Without loss of generality, assume that
$(x,x^{\prime})\in\bar{X_{1}}$ such that $x^{\prime}$ is the sink. Clearly,
$e$ is only contained in a tree $T_{i}^{\prime}$ if
$f_{(x,x^{\prime})}(y)=v_{i}$. Since, $f_{(x,x^{\prime})}$ is a bijection and
$v_{i}$ is unique for $T_{i}^{\prime}$, there is at most one $T_{i}^{\prime}$
containing $e$. Hence, the spanning trees are edge disjoint.

∎

###  4.4. Maximal Solutions Using Additional Edges

Figure 2. The constructions producing the maximal solution when $r_{1}=t_{1}$
and $r_{2}=t_{2}$ are shown above. The legend depicts the choices of vertices
and edges used to construct these EDSTs. The constructions producing a
universal solution of $t_{1}+t_{2}-2$ EDSTs can be seen as generalizations of
Constructions 4.5.3 and 4.5.4, where we allow $v_{i}$ to be an arbitrary
vertex in $V_{s}$ that is unique for each $i$.

In this section, we show that under certain conditions, we can construct
additional trees beyond what universal solution (Section 4.3) does, and
achieve the maximal number of EDSTs in the star product.

Recall notation from Section 4.2. We denote by $N_{s}$ the subgraph of $G_{s}$
whose vertex set is $V_{s}$ and edge set is the set of $r_{1}$ non-tree edges
with respect to the set of spanning trees $\mathbf{X}$. Similarly, $N_{n}$ is
the subgraph of $G_{n}$ whose vertex set is $V_{n}$ and edge set is the set of
$r_{2}$ non-tree edges with respect to $\mathbf{Y}$.

First, we present preliminary results showing connectivity provided by non-
tree edges in a graph with a set of maximal EDSTs.

######  Lemma 4.4.1.

(Ku et al., 2003) Let $G=(V,E)$ be a graph with a maximal number $t$ of EDSTs
and $r$ non-tree edges . There exists a set $\mathbf{X}$ of $t$ EDSTs in $G$
for which the subgraph of $N_{G}$ induced by non-tree edges satisfies the
following: there exists a subset $U\subseteq V$ of $r$ vertices such that
every vertex in $U$ has a path in $N_{G}$ to a vertex in $V\setminus U$.

Lemma 4.4.1 is useful as it means that we can pick special subsets of vertices
$U_{s}$ so that $N_{s}$ has paths from any vertex within $U_{s}$ to a vertex
outside of $U_{s}$. This will be vital to our construction in the following
way: if we can join supernodes $V_{s}\setminus U_{s}$ to a connected
component, we can use edges formed from $N_{s}$ to join all vertices in
$U_{G}$ to the same connected component. Thus, edges incident with $U_{s}$ in
$X_{i}$ can be used for the construction of first $t_{1}+t_{2}-2$ trees (as in
the Universal solution), and $N_{s}$ can be used to connect $U_{s}$ in an
additional tree. Similarly, non-tree edges in $G_{n}$ can also be used to
obtain another additional tree.

Note that not every set of maximal EDSTs in $G_{s}$ and $G_{n}$ will allow
such special subsets. However, we can construct the required EDSTs satisfying
Lemma 4.4.1, starting from any set of maximal EDSTs, as shown in (Ku et al.,
2003). For brevity, we do not repeat the construction of such EDSTs and refer
the reader to (Ku et al., 2003).

The next lemma provides a condition on non-tree edges that guarantees
maximality of EDSTs.

######  Lemma 4.4.2.

Using the setup from Lemma 4.4.1, $t$ is maximal when $r\leq t$.

###### Proof.

Consider a graph $G=(V,E)$ with $m=\lvert V\rvert$ vertices, $t$ EDSTs and $r$
non-tree edges. $G$ has at most $t(m-1)+r\leq mt$ edges. Since an $m$ node
graph can have at most $\frac{m(m-1)}{2}$ edges, $t\leq\frac{m-1}{2}$.
Clearly, the number of EDSTs in $G$ can be at most
$\lfloor\frac{mt}{m-1}\rfloor\leq\lfloor t+\frac{t}{m-1}\rfloor\leq\lfloor
t+\frac{m-1}{2(m-1)}\rfloor\leq t$. Hence, $t$ is maximal. ∎

###  4.5. A Maximal Solution when $r_{1}=t_{1}$ and $r_{2}=t_{2}$

First, we build upon the construction from Section 4.3, carefully selecting
edges from the previous construction. We then build two additional trees.

######  Theorem 4.5.1.

If $r_{1}\geq t_{1}$ and $r_{2}\geq t_{2}$, then we can construct
$t_{1}+t_{2}$ EDSTs in $G_{s}*G_{n}$.

######  Theorem 4.5.2.

If $r_{1}=t_{1}$ and $r_{2}=t_{2}$, then the $t_{1}+t_{2}$ EDSTs constructed
above are maximal.

We show Theorem 4.5.1 for the case when $r_{1}=t_{1}$ and $r_{2}=t_{2}$.
Clearly, this is true if there are more edges in $r_{1}$ and $r_{2}$. Then by
Lemma 4.4.2, $r_{1}=t_{1}$ and $r_{2}=t_{2}$ implies that $t_{1}$ and $t_{2}$
are maximal in $G_{s}$ and $G_{n}$, respectively, and we can invoke Lemma
4.4.1.

Our first construction is a special case of Construction 4.3.2, where we
carefully choose the supernodes $u_{i}$.

######  Construction 4.5.3.

Construct spanning trees $T_{i|2\leq i\leq t_{1}}$. Construction of $T_{i}$ is
via $X_{i}$ and $Y_{1}$ for all $2\leq i\leq t_{1}$. For each $2\leq i\leq
t_{1}$, choose a unique $u_{i}\in U_{s}\setminus\\{o\\}$ such that
$u_{i}=u_{j}$ iff $i=j$.

Intuitive Construction: We construct all edges formed from $X_{i}$, forming a
disconnected spanning graph. We then connect the graph using a copy of $Y_{1}$
in exactly one supernode. We select the supernode $u_{i}\in
U_{s}\setminus\\{o\\}$ since our additional two trees will require
constructing $Y_{1}$ in the other supernodes. This is depicted in Figure 2.

Mathematical Construction: Formally, we construct the spanning tree $T_{i}$
from the union of the following edge sets:

(5) $\displaystyle\\{((u_{i},y),(u_{i},y^{\prime}))\ |\ (y,y^{\prime})\in
E(Y_{1})\\}$ (6) $\displaystyle\\{((x,h),(x^{\prime},f_{x,x}(h)))\ |\
(x,x^{\prime})\in E(X_{i}),h\in V_{n}\\},$

where $2\leq i\leq t_{1}$, $u_{i}\in U_{s}\setminus\\{o\\}$ and $u_{i}=u_{j}$
implies $i=j$.

Our second construction is a special case of Construction 4.3.3, where we
carefully select the incident vertices $v_{i}$ in sink supernodes.

######  Construction 4.5.4.

Construct spanning trees $T_{i|2\leq i\leq t_{2}}^{\prime}$. Construction of
$T_{i}^{\prime}$ via $Y_{i}$ and $X_{1}$ for all $2\leq i\leq t_{2}$. For each
$2\leq i\leq t_{2}$, choose a unique $v_{i}\in U_{n}\setminus\\{o^{\prime}\\}$
such that $v_{i}=v_{j}$ iff $i=j$.

Intuitive Construction: We build $Y_{i}$ in each supernode, then connect all
supernodes using edges formed from $\bar{X}_{1}$ similar to Construction
4.3.3. In order to maintain edge-disjointness amongst these trees, as well as
the two additional trees, we select the incident vertex $v_{i}$ inside sink
supernodes such that $v_{i}\in U_{n}\setminus\\{o^{\prime}\\}.$ This is
depicted in Figure 2.

Mathematical Construction: Formally, we construct the spanning tree
$T_{i}^{\prime}$ from the union of the following edge sets:

(7) $\displaystyle\\{((x,f_{(x,x^{\prime})}^{-1}(v_{i})),(x^{\prime},v_{i}))\
|\ (x,x^{\prime})\in\bar{X}_{1}\\}\ \text{and}$ (8)
$\displaystyle\\{((x,y),(x,y^{\prime}))\ |\ x\in V_{s},(y,y^{\prime})\in
E(Y_{i})\\},$

where $2\leq i\leq t_{2}$, $v_{i}\in U_{n}\setminus\\{o^{\prime}\\}$ and
$v_{i}=v_{j}$ if and only if $i=j$.

######  Construction 4.5.5.

Construction via $X_{1}$, $Y_{1}$, $o$, and $N_{n}$

Intuitive Construction: In the previous constructions, we have used $Y_{1}$ in
all supernodes in $U_{s}\setminus\\{o\\}$ and have used all edges formed from
$\bar{X}_{1}$ incident with a vertex in set $U_{n}\setminus\\{o^{\prime}\\}$
in the sink supernode. This construction will use the instance of $Y_{1}$ in
$o$, instances of $N_{n}$ in all other supernodes, and all edges formed from
$\bar{X}_{1}$ incident with the set $V_{n}\setminus{U_{n}}$ in sink
supernodes. Thus, we will ensure edge disjointness from previous
constructions.

Note that this construction spans all vertices in $G^{*}$. $N_{n}$ instances
inside the supernodes connect every vertex in $U_{n}$ to some vertex in
$V_{n}\setminus U_{n}$. For each supernode, vertices in $V_{n}\setminus U_{n}$
are connected to some vertex in supernode $o$ by the edges formed from
$\bar{X}_{1}$ used in this construction. Since all vertices in $o$ are
connected by $Y_{1}$, we get a connected spanning subgraph. Figure 2 depicts
this construction.

Mathematical Construction: We construct the subgraph of $G^{*}$ formed by the
union of the following edge sets:

(9) $\displaystyle\\{((o,y),(o,y^{\prime}))\ |\ (y,y^{\prime})\in E(Y_{1})\\}\
$ (10) $\displaystyle\\{((x,n),(x,n^{\prime}))\ |\ (n,n^{\prime})\in
E(N_{n}),x\in V_{s}\setminus\\{o\\}\\}\ $ (11)
$\displaystyle\\{((x,f_{(x,x^{\prime})}^{-1}(v)),(x^{\prime},v))\ |\
(x,x^{\prime})\in E(\bar{X}_{1}),v\in V_{n}\setminus U_{n}\\}.$

######  Construction 4.5.6.

Construction via $X_{1}$, $Y_{1}$, $o^{\prime}$, and $N_{s}$

Intuitive Construction: In the previous constructions, we have used $Y_{1}$ in
all supernodes in $U_{s}$ and have used all edges formed from $\bar{X}_{1}$
incident with a vertex in set $V_{n}\setminus\\{o^{\prime}\\}$ in the sink
supernodes. For this last construction, we use an instance of $Y_{1}$ in all
supernodes $u\in V_{s}\setminus U_{s}$. To connect supernodes, we will use all
edges formed from $N_{s}$ and remaining edges from $\bar{X}_{1}$ that are
incident with vertex $o^{\prime}$ in sink supernodes.

All vertices in supernodes that do not have an instance of $Y_{1}$ will be
connected to supernodes in $V_{s}\setminus U_{s}$ via edges formed from
$N_{s}$. The edges formed from $\bar{X}_{1}$ connect all supernodes that
contain $Y_{1}$, which ensures that we produce a connected spanning subgraph.
We depict this construction in Figure 2.

Mathematical Construction: We build this subgraph of $G^{*}$ using a union of
the following edge sets:

(12) $\displaystyle\\{((x,y),(x,y^{\prime}))\ |\ (y,y^{\prime})\in
E(Y_{1}),x\in V_{s}\setminus U_{s}\\}\ $ (13)
$\displaystyle\\{((n,y),(n^{\prime},f_{(n,n^{\prime})}(y)))\ |\
(n,n^{\prime})\in E(\bar{N}_{G}),y\in V_{n}\\}\ $ (14)
$\displaystyle\\{((x,f_{(x,x^{\prime})}^{-1}(o^{\prime})),(x^{\prime},o^{\prime}))\
|\ (x,x^{\prime})\in E(\bar{X}_{1})\\}.$

######  Remark 4.5.7.

Constructions 4.5.5 and 4.5.6 may not be acyclic. However, a quick BFS on the
subgraphs can produce a spanning tree if these subgraphs are spanning in
$G^{*}$.

Constructions 4.5.3 and 4.5.4 clearly form spanning trees in $G^{*}$, as shown
in the proof for Theorem 4.3.1. Next, we formally prove that additional
Constructions 4.5.5 and 4.5.6 also form spanning subgraphs of $G^{*}$.

######  Lemma 4.5.8.

Constructions 4.5.5 and 4.5.6 are connected subgraphs of $G^{*}$ with the same
vertex set as $G^{*}$. Moreover, these two graphs are edge-disjoint.

###### Proof.

First, consider Construction 4.5.5. We will use induction to show that the
resulting graph satisfies the lemma. From the edges in (9), all vertices in
supernode $o$ are connected by spanning tree $Y_{1}$. Now consider a neighbor
$x^{\prime}$ of $o$ in $\bar{X}_{1}$ and pick some $v\in V_{n}$. We will show
that $(x^{\prime},v)$ is connected to supernode $o$. Since this choice of
vertex was arbitrary, by induction, the result will be hold. If $v\in
V_{n}\setminus U_{n}$, then there exists a direct edge from the set
$\eqref{eq:X1_in_VH_minus_UH}$ connecting supernode $o$ to $(x^{\prime},v)$.
If $v\in U_{n}$, by Lemma 4.4.1, there exists a path within graph $N_{n}$ from
$v$ to $w\in V_{n}\setminus U_{n}$. Since $w\in V_{n}\setminus U_{n}$, there
exists a direct edge from supernode $o$ to $(x^{\prime},w)$. Concatenating the
two paths gives the result.

Next, consider Construction 4.5.6. First, we show that all supernodes are
internally connected. Clearly, supernodes in $V_{s}\setminus U_{s}$ are
connected because of the $Y_{1}$ instance within them. Consider a supernode
$u\in U_{s}$. It is connected to some $u^{\prime}\in V_{s}\setminus U_{s}$ via
a path in $N_{s}$. Since all edges formed from non-tree edges in $N_{s}$ are
used in this construction, every vertex in supernode $u$ connects to some
vertex in supernode $u^{\prime}$. Since $u^{\prime}\in V_{s}\setminus U_{s}$,
it is connected by $Y_{1}$ internally. Hence, vertices in supernode $u$ are
connected.

Now we show that all supernodes are connected, hence the construction is a
spanning subgraph of $G^{*}$. Consider $x^{\prime}$, a neighbor of root $o$ in
$\bar{X}_{1}$. There is an edge between these supernodes by (14), thus these
supernodes are connected. An inductive argument on the levels of the tree
$\bar{X}_{1}$ gives the result.

Finally, we show that the two graphs are edge-disjoint. This reduces to
showing i) (9) and (12) are edge-disjoint and ii) (11) and (14) are edge-
disjoint. Since $o\in U_{s}$ and $o^{\prime}\in U_{n}$, this is clear. ∎

###### Proof of Theorem 4.5.1.

It remains to show that when $N_{s}$ and $N_{n}$ have at least $t_{1}$ and
$t_{2}$ edges respectively, then we can produce $t_{1}+t_{2}$ EDSTs on
$G^{*}$.

Constructions 4.5.3 and 4.5.4 produce $t_{1}-1$ and $t_{2}-1$ EDSTs
respectively. From Lemma 4.4.1, if $r_{1}\geq t_{1}$ and $r_{2}\geq t_{2}$,
then $|U_{s}|\geq t_{1}$ and $|U_{n}|\geq t_{2}$. Hence, there are sufficient
choices for unique supernodes $u_{i}\in U_{s}\setminus\\{o\\}$ in Construction
4.5.3, and sufficient choices for unique vertices $v_{i}\in
U_{n}\setminus\\{o^{\prime}\\}$ in Construction 4.5.4.

From Remark 4.5.7, we can produce spanning trees of $G^{*}$ from Constructions
4.5.5 and 4.5.6. So it remains to show that the additional two trees share no
edges with the trees from Constructions 4.5.3 or 4.5.4. As in Lemma 4.5.8, we
only need to compare the sets (9) and (12) with (5) for each
$i=2,\ldots,t_{1}$. We also need to compare (11) and (14) with (7) for each
$j=2,\ldots,t_{2}$. Notice that in (5) we use supernodes from
$U_{s}\setminus\\{o\\}$, in (9) we use supernode $o$, and in (12) we use
$V_{s}\setminus U_{s}$ to construct $Y_{1}$. Thus no edges are used in
multiple trees between these sets. A similar evaluation of (7), (11), and (14)
shows that these sets are disjoint as well. Thus all $t_{1}+t_{2}$ spanning
trees are edge-disjoint. ∎

###### Proof of Theorem 4.5.2.

We have already shown that our construction gives $t_{1}+t_{2}$ EDSTs of
$G^{*}$ when $r_{1}\geq t_{1}$ and $r_{2}\geq t_{2}$. Here, we show that this
is maximal when $r_{1}=t_{1}$ and $r_{2}=t_{2}$. The proof is similar to that
of Lemma 4.4.2. Let $m_{1}=\lvert V_{s}\rvert$ and $m_{2}=\lvert V_{n}\rvert$
denote the number of vertices in factor graphs. The number of edges in $G_{s}$
and $G_{n}$ is at most $m_{1}t_{1}$ and $m_{2}t_{2}$, and is at most
$m_{1}m_{2}(t_{1}+t_{2})$ in the star product $G^{*}$. Since each EDST in
$G^{*}$ uses $m_{1}m_{2}-1$ edges, the number of non-tree edges in $G^{*}$ is
at most $m_{1}m_{2}(t_{1}+t_{2})-(m_{1}m_{2}-1)(t_{1}+t_{2})=t_{1}+t_{2}$,
which is the same as the number of EDSTs. Therefore, by Lemma 4.4.2, the set
of $t_{1}+t_{2}$ EDSTs is maximal.∎

Note that Construction 4.5.5 only requires that $r_{1}\geq t_{1}$, with no
constraints on $r_{2}$, and Construction 4.5.6 only requires that $r_{2}\geq
t_{2}$, with no requirements for $r_{1}$. Thus if only one of $r_{1}\geq
t_{1}$ or $r_{2}\geq t_{2}$, we can obtain $t_{1}+t_{2}-1$ EDSTs. We state
this as a theorem below.

######  Theorem 4.5.9.

If $r_{1}\geq t_{1}$ or $r_{2}\geq t_{2}$, then we can construct
$t_{1}+t_{2}-1$ EDSTs in $G_{s}*G_{n}$.

It remains to understand the case when $r_{1}<t_{1}$ and $r_{2}<t_{2}$. We
consider this in the next section, and show a completely different
construction that provides $t_{1}+t_{2}-1$ EDSTs, at least under a certain
condition on the bijections $f_{(x,x^{\prime})}.$

###  4.6. A Maximal Solution When $r_{1}<t_{1}$ and $r_{2}<t_{2}$

We know at least $t_{1}+t_{2}-2$ EDSTs exist for any choice of graphs $G_{s}$
and $G_{n}$ by Theorem 4.3.1 and that $t_{1}+t_{2}-1$ EDSTs exists if
$r_{1}\geq t_{1}$ or $r_{2}\geq t_{2}$. However, in order to get
$t_{1}+t_{2}-1$ EDSTs as in Theorem 4.6.2 when $r_{1}<t_{1}$ and
$r_{2}<t_{2}$, we will need to modify Constructions 4.3.2 and 4.3.3 since they
do not save enough edges to produce one more tree. We present such a
modification which allows us to get $t_{1}+t_{2}-1$ trees inspired by (Ku et
al., 2003).

While their paper gives this many trees without conditions, the “twisted”
edges of the star product makes connectivity more difficult to achieve. Our
construction will have conditions on the bijections $f_{(x,x^{\prime})}$.
Since a star product exists for each choice of $f$, this condition should
hopefully be mild.

Consider the tree $Y_{1}$. We choose an arbitrary vertex $o^{\prime}\in
V_{n}$. For construction purposes, we consider a directed version of $Y_{1}$,
denoted as $\bar{Y}_{1}$, rooted at the vertex $o^{\prime}\in V_{n}$ with
directed edges such that each edge goes from a parent to a child, where parent
is the vertex closer to the root $o^{\prime}$ than the child. The main idea
behind this construction is to partition the edges of $Y_{1}$ into two
subsets, placing the subsets in particular supernodes to guarantee the edges
needed for an additional tree.

Partition the edges of $Y_{1}$ into two subsets, $S_{1}$ and $S_{2}$, each of
size at least $t_{2}-2+|V(S_{1})\cap V(S_{2})|$, such that no vertex in
$V(S_{1})$ is an ancestor of a vertex in $V(S_{2})$ where $V(S_{1})$ and
$V(S_{2})$ are the vertices incident to the edges in $S_{1}$ and $S_{2}$
respectively. Intuitively, we are separating the top and bottom of $Y_{1}$ by
cutting the branches. Note that different branches may be cut at different
levels of the tree. A possible such partition by Ku et al. can be found in (Ku
et al., 2003). Note that by definition every vertex in $V(S_{1})$ is connected
to a vertex in $V(S_{2})$ by edges in $S_{1}$ and the edges of $S_{2}$ form a
subtree of $Y_{1}$. The following property guarantees the $t_{1}+t_{2}-1$
EDSTs.

######  Property 4.6.1.

A star product $G^{*}$ has Property 4.6.1 if for some EDST
$Y_{i}\in\mathbf{Y}$ with edge partition $S_{1}$ and $S_{2}$ as above, we have
$f_{(x,x^{\prime})}(V(S_{j}))=V(S_{j})$ for all EDST $X_{i}\in\mathbf{X}$ and
$(x,x^{\prime})\in E(X_{i})$.

Intuitively, $G^{*}$ has Property 4.6.1 if we can partition an EDST of $G_{n}$
so that the edges between supernodes connect vertices in $V(S_{1})$ to
vertices in $V(S_{1})$ and vertices in $V(S_{2})$ to vertices in $V(S_{2})$.

Property 4.6.1 is quite powerful; all Cartesian products satisfy this
property, as well as some star products.

We let $Y_{1}$ be such EDST, if it exists. Let $I=V(S_{1})\cap V(S_{2})$.
Since no vertex in $V(S_{1})$ is an ancestor of a vertex in $V(S_{2})$, we
have $I\neq\emptyset$. Note that the partition on $Y_{1}$ and the definition
of Property 4.6.1 forces $f_{(x,x^{\prime})}(I)=I$ for all $(x,x^{\prime})\in
E(X_{i})$.

######  Theorem 4.6.2.

If $G^{*}$ satisfies Property 4.6.1, we can construct $t_{1}+t_{2}-1$ EDSTs
without any constraints on $r_{1}$ or $r_{2}$. Moreover, this construct of
$t_{1}+t_{2}-1$ EDSTs is maximal when $r_{1}=0$ and $r_{2}=0.$

Once we show a construction that produces $t_{1}+t_{2}-1$ EDSTs in $G^{*}$, we
use the following theorem to obtain our maximality result.

######  Theorem 4.6.3.

(Ku et al., 2003, Corollaries 1 and 2) If $r_{1}=0$ and $r_{2}=0$, then the
maximal number of EDSTs in $G^{*}$ is $t_{1}+t_{2}-1$.

The proof of Theorem 4.6.3 holds for a range of $r_{1}$ and $r_{2}$. If
$r_{1}=0$, one can show that maximality holds for $0\leq r_{2}\leq t_{2}$. A
similar range holds when $r_{2}=0$.

To prove Theorem 4.6.2, we first describe modifications on Constructions 4.3.2
and 4.3.3 that produce a set of $t_{1}+t_{2}-2$ EDSTs, while leaving enough
remaining edges to construct one additional EDST without relying on the use of
non-tree edges of the factor graphs. We then construct the additional tree.
Then we show that these sets of trees can share no edges. As in Section 4.3,
it is important to establish direction in the EDSTs in $\mathbf{X}$. We choose
an arbitrary vertex $o\in V_{s}$. In our constructions, we will define
directed trees rooted at $o$ for each $X_{i}\in\mathbf{X}$, which we will
label $\bar{X}_{i}$. Partition the vertices of $V_{s}\setminus\\{o\\}$ into
balanced sets $R_{1}$ and $R_{2}$. For each $2\leq i\leq t_{1}$, construct the
triples $(i,a_{i},b_{i})$ where $a_{i}\in R_{1}$ and $b_{i}\in R_{2}$ such
that no two triples have the same $i,a_{i},$ or $b_{i}$. For each $2\leq i\leq
t_{2}$, construct the triples $(i,c_{i},d_{i})$ where $c_{i}\in
V(S_{1})\setminus I$ and $d_{i}\in V(S_{2})\setminus I$ such that no two
triples have the same $i,c_{i},$ or $d_{i}$.

The list below gives all notations used in our constructions:

  * •

$\mathbf{X}$, a set of maximal EDSTs in $G_{s}$ of size $t_{1}$

  * •

$\mathbf{Y}$, a set of maximal EDSTs in $G_{n}$ of size $t_{2}$

  * •

$R_{1}$ and $R_{2}$, balanced partition of the vertices
$V_{s}\setminus\\{o\\}$

  * •

$S_{1}$ and $S_{2}$, partition of $Y_{1}$ edges each of size at least
$t_{2}-2+|I|$ such that no vertex in $V(S_{1})$ is an ancestor of a vertex in
$V(S_{2})$

  * •

$o$, an arbitrary vertex in $V_{s}$

  * •

$o^{\prime}$, an arbitrary vertex in $V_{n}$

  * •

$I$, the set of vertices $V(S_{1})\cap V(S_{2})$

  * •

$(i,a_{i},b_{i})$, unique triples from vertices in $R_{1}$ and $R_{2}$

  * •

$(i,c_{i},d_{i})$, unique triples from vertices in $V(S_{1})\setminus I$ and
$V(S_{2})\setminus I$

Figure 3. The constructions producing the maximal solution when $r_{1}=0$ and
$r_{2}=0$ is shown above. The legend depicts the choices of vertices and edges
used to construct these EDSTs in a star product $G^{*}$ that satisfies
Property 4.6.1.

Our first construction is similar to Construction 4.3.2, but instead
partitioning the edges of $Y_{1}$ between two supernodes to connect the
subgraph.

######  Construction 4.6.4.

Construct spanning trees $T_{i|2\leq i\leq t_{1}}$. Construction of $T_{i}$ is
via $X_{i}$ and $Y_{1}$ for $2\leq i\leq t_{1}$.

Intuitive Construction: For tree $T_{i}$, we construct all edges formed from
$X_{i}$. This forms a disconnected spanning graph. We then connect the graph
using a copy of $S_{1}$ in one supernode and a copy of $S_{2}$ in another. We
select the supernodes $a_{i}$ and $b_{i}$, respectively, since our final
construction will require constructing the unused $Y_{1}$ edges in both
supernodes. Since every vertex in $V(S_{1})$ is connected to a vertex in
$V(S_{2})$ by edges in $S_{1}$ and the edges of $S_{2}$ form a subtree of
$Y_{1}$, Property 4.6.1 guarantees connectedness by mapping vertices in the
edge partition $S_{1}$ and $S_{2}$ back to their respective sets. We depict
this in Figure 3.

Mathematical Construction: Formally, the following edge set defines the
subgraph.

(15) $\displaystyle\\{((a_{i},s_{1}),(a_{i},s_{1}^{\prime}))\ |\
(s_{1},s_{1}^{\prime})\in S_{1}\\},$ (16)
$\displaystyle\\{((b_{i},s_{2}),(b_{i},s_{2}^{\prime}))\ |\
(s_{2},s_{2}^{\prime})\in S_{2}\\},$ (17)
$\displaystyle\\{((x,y),(x^{\prime},f_{(x,x^{\prime})}(y)))\ |\
(x,x^{\prime})\in E(X_{i}),y\in V_{n}\\}.$

where $2\leq i\leq t_{1}$.

######  Construction 4.6.5.

Construct spanning trees $T_{i|2\leq i\leq t_{2}}^{\prime}$. Construction of
$T_{i}^{\prime}$ via $Y_{i}$ and $X_{1}$ for all $2\leq i\leq t_{2}$.

Intuitive Construction: For tree $T_{i}^{\prime}$, we build $Y_{i}$ in each
supernode, then connect all supernodes using edges formed from $X_{1}$ similar
to Construction 4.3.3. The uniqueness of the triples $(i,c_{i},d_{i})$ allows
for edge-disjointness amongst these trees, as well as the final tree
constructed. We connect sink nodes of $\bar{X}_{1}$ in $R_{1}$ by a single
edge defined by $d_{i}$ and sink nodes in $R_{2}$ by a single edge defined by
$c_{i}$. We depict this in Figure 3.

Mathematical Construction: Formally, we use the following edge sets to define
the subgraph, where $2\leq i\leq t_{2}.$

(18) $\displaystyle\\{((x,f_{(x,x^{\prime})}^{-1}(c_{i})),(x^{\prime},c_{i}))\
|\ (x,x^{\prime})\in E(\bar{X}_{1}),x^{\prime}\in R_{2}\\},$ (19)
$\displaystyle\\{((x,f_{(x,x^{\prime})}^{-1}(d_{i})),(x^{\prime},d_{i}))\ |\
(x,x^{\prime})\in E(\bar{X}_{1}),x^{\prime}\in R_{1}\\},$ (20)
$\displaystyle\\{((x,y),(x,y^{\prime}))\ |\ x\in V_{s},(y,y^{\prime})\in
E(Y_{i})\\}.$

######  Construction 4.6.6.

Construction spanning tree $T$. Construction of $T$ via $X_{1}$ and $Y_{1}$.

Intuitive Construction: For tree $T$, we build $Y_{1}$ in supernode $o$ and
build $S_{2}$ and $S_{1}$ in each $r_{1}\in R_{1}$ and $r_{2}\in R_{2}$
supernode, respectively. For each edge $(x,x^{\prime})$ in $\bar{X}_{1}$, if
the sink supernode $x^{\prime}$ is in $R_{1}$, we use all edges between
supernodes $x$ and $x^{\prime}$ that are incident with $V(S_{1})$ in supernode
$x^{\prime}$. If the sink supernode is in $R_{2}$, we use all edges between
$x$ and $x^{\prime}$ that are incident with $V(S_{2})$. Since every vertex in
$V(S_{1})$ is connected to a vertex in $V(S_{2})$ be edges in $S_{1}$ and the
edges of $S_{2}$ form a subtree of $Y_{1}$, Property 4.6.1 guarantees
connectedness by mapping vertices in the edge partition $S_{1}$ and $S_{2}$
back to their respective sets. We depict this in Figure 3.

Mathematical Construction: Formally, we use the following edge sets to define
the subgraph.

(21) $\displaystyle\\{((o,y),(o,y^{\prime}))\ |\ (y,y^{\prime})\in
E(Y_{1})\\},$ (22) $\displaystyle\\{((r_{1},s_{2}),(r_{1},s_{2}^{\prime}))\ |\
r_{1}\in R_{1},(s_{2},s_{2}^{\prime})\in S_{2}\\},$ (23)
$\displaystyle\\{((r_{2},s_{1}),(r_{2},s_{1}^{\prime}))\ |\ r_{2}\in
R_{2},(s_{1},s_{1}^{\prime})\in S_{1}\\},$ (24)
$\displaystyle\\{((x,f_{(x,x^{\prime})}^{-1}(s_{1})),(x^{\prime},s_{1}))\ |\
(x,x^{\prime})\in E(\bar{X}_{1}),x^{\prime}\in R_{1},s_{1}\in V(S_{1})\\},$
(25) $\displaystyle\\{((x,f_{(x,x^{\prime})}^{-1}(s_{2})),(x^{\prime},s_{2}))\
|\ (x,x^{\prime})\in E(\bar{X}_{1}),x^{\prime}\in R_{2},s_{2}\in V(S_{2})\\}.$

Construction 4.6.5 does not require the use of Property 4.6.1 and, by similar
reasons as in Construction 4.5.4, can be seen to produce $t_{2}-1$ EDSTs. For
Constructions 4.6.4 and 4.6.6, we will require the use of Property 4.6.1 which
we prove in the following lemma.

######  Lemma 4.6.7.

Constructions 4.6.4, 4.6.5, and 4.6.6 are connected spanning subgraphs of
$G^{*}$.

###### Proof.

First, we show Construction 4.6.4 produces $t_{1}-1$ connected spanning
subgraphs in $G^{*}$. Consider the subgraph $T_{i}$ with $S_{1}$ in supernode
$a_{i}$ and $S_{2}$ in supernode $b_{i}$ via (15) and (16), respectively.
Since we chose the triple $(i,a_{i},b_{i})$ such that $a_{i}=a_{j}$ or
$b_{i}=b_{j}$ iff $i=j$, for each $T_{i}$ we have a unique $a_{i}$ and
$b_{i}$. The edges in (17), which are defined by $f_{(x,x^{\prime})}$ for
$(x,x^{\prime})\in X_{i}$, cover all vertices in the graph. Thus, we have
unique $t_{1}-1$ spanning subgraphs. To show all $t_{1}-1$ are connected,
consider a node $(x,y)$ in $G^{*}$. If $y\in V(S_{2})$, then there exists a
path in (17) via $X_{i}$ to a node $(b_{i},s_{2})$ where $s_{2}\in V(S_{2})$
by Property 4.6.1. If $y\in V(S_{1})$, then there exists a path in (17) via
$X_{i}$ to a node $(a_{i},s_{1})$ where $s_{1}\in V(S_{1})$ by Property 4.6.1.
By the definition of the partition, every vertex in $V(S_{1})$ has a path to
some vertex in $V(S_{2})$ and so there is a path in $S_{2}$ to that vertex in
$V(S_{1})$ via only edges in $S_{2}$. Thus, after following the path from
$(a_{i},s_{1})$ to $(b_{i},s_{1}^{\prime})$ for some $s_{1}^{\prime}\in
V(S_{1})$, we can follow a path in (16) from $(b_{i},s_{1}^{\prime})$ to
$(b_{i},s_{2}^{\prime})$ for some $s_{2}^{\prime}\in V(S_{2})$. Thus every
vertex in $G^{*}$ is connected to $S_{2}$. Since $S_{2}$ is a tree, then the
entire spanning subgraph is connected.

Notice that Construction 4.6.5 is very similar to Construction 4.3.3, and a
similar inductive proof shows that each is an EDST.

Lastly, we show Construction 4.6.6 produces a connected spanning subgraph $T$
in $G^{*}$. Consider a neighbor $x^{\prime}$ of $o$ and pick some $v\in
V_{n}$. We will show that $(x^{\prime},v)$ is connected to supernode $o$. If
$x^{\prime}\in R_{1}$ then in the supernode $x^{\prime}$ we have constructed
$S_{2}$. If $v\in V(S_{1})$, then there is a direct edge in (24) between
supernode $o$ and $(x^{\prime},v)$ by Property 4.6.1. If $v\in V(S_{2})$, then
since every vertex in $V(S_{1})$ has a path to a vertex in $V(S_{2})$, we can
first follow this path to $(x^{\prime},w)$ for some $w\in V(S_{1})$, then use
the direct edge to supernode $o$. Now suppose $x^{\prime}\in R_{2}$. Then the
supernode contains a copy of $S_{1}$. If $v\in V(S_{2})$, then there is a
direct edge in (25) to supernode $o$ by Property 4.6.1. Else, by the same
logic as before, we can follow a path to $(x^{\prime},w)$ for some $w\in
V(S_{2})$ and then use the direct edge to supernode $o$. We conclude using
induction on the level of the tree $\bar{X}_{1}$.

∎

As in Section 4.4, some of these constructions maybe not by acyclic. By Remark
4.5.7, we can take these constructions to produce spanning trees of $G^{*}$.
We now complete the proof of Theorem 4.6.2 by showing the spanning trees
produces are edge-disjoint.

###### Proof of Theorem 4.6.2.

By Lemma 4.6.7 and Remark 4.5.7, we have $t_{1}+t_{2}-1$ spanning trees of
$G^{*}$. It remains to show disjointness.

Since $\mathbf{X}$ and $\mathbf{Y}$ are sets of EDSTs, we need only compare
(15), (21), (23) for $2\leq i\leq t_{1}$ and (16), (21), (22) for $2\leq i\leq
t_{1}$ and (18), (19), (24), (25) for $2\leq i\leq t_{2}$. Recall that
$a_{i}\in R_{1}$ and $b_{i}\in R_{2}$ for all $i$ where
$V_{s}\setminus\\{o\\}=R_{1}\cup R_{2}$ and $R_{1}\cap R_{2}=\emptyset$. Also,
recall that $E(Y_{1})=E(S_{1})\cup E(S_{2})$ where $E(S_{1})\cap
E(S_{2})=\emptyset$ and $I=V(S_{1})\cap V(S_{2})$. By the partitions of
$V_{s}\setminus\\{o\\}$ and $E(Y_{1})$, for all $2\leq i\leq t_{2}$, we have
that (15), (21), (23) and, for all for $2\leq i\leq t_{1}$, (16), (21), (22)
and, for all $2\leq i\leq t_{2}$, (18), (19), (24), (25) are all disjoint
sets.

Maximality in the case that $r_{1}=0$ and $r_{2}=0$ follows from Theorem
4.6.3. ∎

##  5\. Discussion: Generalizing Properties of Cartesian Product Networks

We have noted that the star product is a generalization of the Cartesian
product, and also have noted that several important emerging networks are in
fact star products. Star product graphs have many benefits for network design.

Inspired by this, in this paper we have shown that maximal or near-maximal
EDSTs may be constructed from a set of EDSTs in factor graphs, which
generalizes a prior result on Cartesian products. This permits efficient
implementation of Allreduce and other important collectives, and fault
tolerance mechanisms.

It seems reasonable that other important and well studied properties of
Cartesian product networks (Youssef, 1991) might also be extended to star
product networks. These include bisection bandwidth (Aroca and Anta, 2014),
path diversity and fault diameter (Day and Al-Ayyoub, 2000), routing
algorithms (Youssef, 1991), deadlock avoidance (KráĽovič et al., 1998), and
resource placement (Imani et al., 2010). Extension of these and other
Cartesian network properties will be an interesting and important area of
future research for the successful implementation of these star product
networks.

## References

  * (1)
  * Ahn et al. (2009) Jung Ho Ahn, Nathan Binkert, Al Davis, Moray McLaren, and Robert S. Schreiber. 2009.  HyperX: Topology, Routing, and Packaging of Efficient Large-Scale Networks. In _Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis_ (Portland, Oregon) _(SC ’09)_. Association for Computing Machinery, New York, NY, USA, Article 41, 11 pages.  https://doi.org/10.1145/1654059.1654101
  * Akiba et al. (2017) Takuya Akiba, Shuji Suzuki, and Keisuke Fukuda. 2017.  Extremely large minibatch sgd: Training resnet-50 on imagenet in 15 minutes.  _arXiv preprint arXiv:1711.04325_ (2017).
  * Alspach et al. (2012) Brian Alspach, Darryn Bryant, and Danny Dyer. 2012.  Paley graphs have Hamilton decompositions.  _Discrete Mathematics_ 312, 1 (2012), 113–118.  https://doi.org/10.1016/j.disc.2011.06.003 Algebraic Graph Theory — A Volume Dedicated to Gert Sabidussi on the Occasion of His 80th Birthday.
  * Aroca and Anta (2014) Jordi Arjona Aroca and Antonio Fernández Anta. 2014.  Bisection (Band)Width of Product Networks with Application to Data Centers.  _IEEE Transactions on Parallel and Distributed Systems_ 25, 3 (2014), 570–580.  https://doi.org/10.1109/TPDS.2013.95
  * Barden et al. (1999) Benjamin Barden, Ran Libeskind-Hadas, Janet Davis, and William Williams. 1999.  On edge-disjoint spanning trees in hypercubes.  _Inform. Process. Lett._ 70, 1 (1999), 13–16.
  * Bermond et al. (1982) J.C. Bermond, C. Delorme, and G. Farhi. 1982.  Large graphs with given degree and diameter III.  _Ann. of Discrete Math._ 13 (1982), 23–32.
  * Besta and Hoefler (2014) Maciej Besta and Torsten Hoefler. 2014.  Slim Fly: A Cost Effective Low-Diameter Network Topology. In _Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis_ (New Orleans, LA, USA). Association for Computing Machinery, New York, NY, USA.
  * Brown (1966) W. G. Brown. 1966.  On Graphs that do not Contain a Thomsen Graph.  _Can. Math. Bull._ 9, 3 (1966), 281–285.  https://doi.org/10.4153/CMB-1966-036-2
  * Cheng et al. (2023) Baolei Cheng, Dajin Wang, and Jianxi Fan. 2023.  Independent Spanning Trees in Networks: A Survey.  _ACM Comput. Surv._ 55, 14s, Article 335 (jul 2023), 29 pages.  https://doi.org/10.1145/3591110
  * Day and Al-Ayyoub (2000) K. Day and A.-E. Al-Ayyoub. 2000.  Minimal fault diameter for highly resilient product networks.  _IEEE Transactions on Parallel and Distributed Systems_ 11, 9 (2000), 926–930.  https://doi.org/10.1109/71.879775
  * Erdős and Rényi (1962) Paul Erdős and Alfred Rényi. 1962.  On a problem in the theory of graphs.  _Publ. Math. Inst. Hungar. Acad. Sci._ 7A (1962), 623–641.
  * Fragopoulou and Akl (1996) Paraskevi Fragopoulou and Selim G. Akl. 1996.  Edge-disjoint spanning trees on the star network with applications to fault tolerance.  _IEEE Trans. Comput._ 45, 2 (1996), 174–185.
  * Hafner (2004) Paul R. Hafner. 2004.  Geometric realisation of the graphs of McKay–Miller–Širáň.  _Journal of Combinatorial Theory, Series B_ 90, 2 (2004), 223–232.  https://doi.org/10.1016/j.jctb.2003.07.002
  * Imani et al. (2010) N. Imani, H. Sarbazi-Azad, and A.Y. Zomaya. 2010.  Resource placement in Cartesian product of networks.  _J. Parallel and Distrib. Comput._ 70, 5 (2010), 481–495.  https://doi.org/10.1016/j.jpdc.2009.06.005
  * KráĽovič et al. (1998) Rastislav KráĽovič, Branislav Rovan, Peter RuŽička, and Daniel štefankovič. 1998.  Efficient deadlock-free multi-dimensional interval routing in interconnection networks. In _Distributed Computing_ , Shay Kutten (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 273–287.
  * Ku et al. (2003) Shan-Chyun Ku, Biing-Feng Wang, and Ting-Kai Hung. 2003.  Constructing edge-disjoint spanning trees in product networks.  _IEEE Transactions on Parallel and Distributed Systems_ 14, 3 (2003), 213–221.  https://doi.org/10.1109/TPDS.2003.1189580
  * Lakhotia et al. (2023a) Kartik Lakhotia, Kelly Isham, Laura Monroe, Maciej Besta, Torsten Hoefler, and Fabrizio Petrini. 2023a.  In-Network Allreduce with Multiple Spanning Trees on PolarFly. In _Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures_ (Orlando, FL, USA) _(SPAA ’23)_. Association for Computing Machinery, New York, NY, USA, 165–176.  https://doi.org/10.1145/3558481.3591073
  * Lakhotia et al. (2023b) Kartik Lakhotia, Laura Monroe, Kelly Isham, Maciej Besta, Nils Blach, Torsten Hoefler, and Fabrizio Petrini. 2023b.  PolarStar: Expanding the Scalability Horizon of Diameter-3 Networks.  arXiv:2302.07217 [cs.NI]
  * Lei et al. (2020) Fei Lei, Dezun Dong, Xiangke Liao, and José Duato. 2020.  Bundlefly: A Low-Diameter Topology for Multicore Fiber. In _Proceedings of the 34th ACM International Conference on Supercomputing_ (Barcelona, Spain) _(ICS ’20)_. Association for Computing Machinery, New York, NY, USA, Article 20, 11 pages.  https://doi.org/10.1145/3392717.3392747
  * Li et al. (2010) Shasha Li, Wei Li, and Xueliang Li. 2010.  The generalized connectivity of complete bipartite graphs.  _Ars Comb._ 104 (2010), 65–79.  https://api.semanticscholar.org/CorpusID:14240977
  * McKay et al. (1998) Brendan D McKay, Mirka Miller, and Jozef Siráň. 1998.  A Note on Large Graphs of Diameter Two and Given Maximum Degree.  _Journal of Combinatorial Theory, Series B_ 74, 1 (1998), 110–118.  https://doi.org/10.1006/jctb.1998.1828
  * Narayanan et al. (2021) Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGresley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, et al. 2021\.  Efficient large-scale language model training on gpu clusters using megatron-lm. In _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_. 1–15.
  * Palmer (2001a) E.M. Palmer. 2001a.  On the spanning tree packing number of a graph: a survey.  _Discrete Mathematics_ 230, 1 (2001), 13–21.  https://doi.org/10.1016/S0012-365X(00)00066-2 Catlin.
  * Palmer (2001b) E.M. Palmer. 2001b.  On the spanning tree packing number of a graph: a survey.  _Discrete Mathematics_ 230, 1 (2001), 13–21.  https://doi.org/10.1016/S0012-365X(00)00066-2 Catlin.
  * Patwary et al. (2019) Mostofa Patwary, Milind Chabbi, Heewoo Jun, Jiaji Huang, Gregory Diamos, and Kenneth Church. 2019.  Language modeling at scale. In _2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE, 590–599.
  * Roskind and Tarjan (1985) James Roskind and Robert E Tarjan. 1985.  A note on finding minimum-cost edge-disjoint spanning trees.  _Mathematics of Operations Research_ 10, 4 (1985), 701–708.
  * Roskind (1983) James Anthony Roskind. 1983.  _Edge disjoint spanning trees and failure recovery in data communication networks_.  Ph. D. Dissertation. Massachusetts Institute of Technology.
  * Sergeev and Del Balso (2018) Alexander Sergeev and Mike Del Balso. 2018.  Horovod: fast and easy distributed deep learning in TensorFlow.  _arXiv preprint arXiv:1802.05799_ (2018).
  * Youssef (1991) Abdou Youssef. 1991.  Cartesian Product Networks. In _International Conference on Parallel Processing_.  https://api.semanticscholar.org/CorpusID:8249681
  * Zhao et al. (2023) Liangyu Zhao, Siddharth Pal, Prithwish Basu, Joud Khoury, and Arvind Krishnamurthy. 2023.  Bandwidth Optimal Pipeline Schedule for Collective Communication.  _arXiv preprint arXiv:2305.18461_ (2023).

##  Appendix A Combinatorial Calculations: A Helpful Lemma

The formula for the maximum number of EDSTs in a graph is:

$\left\lfloor\frac{e}{v-1}\right\rfloor,$

where $e$ is the number of edges and $v$ is the number of vertices. Often, $e$
and $v$ share some factor $c$, i.e., $e=ac$ and $v=bc$ for some $a$ and $b$.
If that is so, we may immediately apply the following lemma.

######  Lemma A.0.1.

Let $e$ and $v$ be real numbers, with $a$, $b$ and $c$ real numbers such that
$e=ac$ and $v=bc$. Then

$\frac{e}{v-1}=\frac{ac}{bc-1}=\frac{a}{b}+\frac{a}{b(bc-1)}.$

Our strategy throughout this section is to find a common factor $c$ shared by
the integers $e$ and $v$, and then apply the lemma.

Intuitively, it seems believable that $\frac{e}{v-1}$ will be only a little
larger than $\frac{e}{v}$ when $e$ and $v$ are reasonably large. We see that
if

$\frac{a}{b(bc-1)}<\left\lceil\frac{a}{b}\right\rceil-\frac{a}{b},$

the left fraction does not contribute to the floor, and we have that

$\left\lfloor\frac{ac}{bc-1}\right\rfloor=\left\lfloor\frac{a}{b}\right\rfloor.$

In particular, when $b=2$, if we can show that

$0<\frac{a}{b(bc-1)}<\frac{1}{2},$

we get that the maximum number of EDSTs is
$\left\lfloor\frac{a}{b}\right\rfloor$.

##  Appendix B Combinatorial Calculations: Factor Graphs

In this section, we calculate parameters on the common factor graphs that are
seen throughout this paper. Table 4 summarizes the results in this section.

Graph | Parameters | Vertices | Edges | ST edges | t | r
---|---|---|---|---|---|---
| $q=4k+1$ | $4k+1$ | $k(4k+1)$ | $4k$ | $k$ | $k$
| $q=4k$ | $4k$ | $4k^{2}$ | $4k-1$ | $k$ | $k$
C($q$) | $q=4k-1$ | $4k-1$ | $k(4k-1)$ | $4k-2$ | $k$ | $k$
| $q=4k+1$ | $2q$ | $q^{2}$ | $2q-1$ | $2k$ | $6k+1$
| $q=4k$ | $2q$ | $q^{2}$ | $2q-1$ | $2k$ | $2k$
$K_{q,q}$ | $q=4k-1$ | $2q$ | $q^{2}$ | $2q-1$ | $2k-1$ | $6k-2$
| $q=4k+1$ | $2q^{2}$ | $\frac{q^{2}(3q-1)}{2}$ | $2q^{2}-1$ | $3k$ | $q^{2}+3k$
| $q=4k$ | $2q^{2}$ | $\frac{3q^{3}}{2}$ | $2q^{2}-1$ | $3k$ | $3k$
$H_{q}$ | $q=4k-1$ | $2q^{2}$ | $\frac{q^{2}(3q-1)}{2}$ | $2q^{2}-1$ | $3k-1$ | $q^{2}+3k-1$
| $m=2\ell$ | $2\ell$ | $\ell(2\ell-1)$ | $2\ell-1$ | $\ell$ | $0$
$K_{m}$ | $m=2\ell+1$ | $2\ell+1$ | $\ell(2\ell+1)$ | $2\ell$ | $\ell$ | $\ell$
|  $d$ even | $2d$ | $d^{2}$ | $2d-1$ | $\frac{d}{2}$ | $\frac{d}{2}$
BDF($d$) |  $d$ odd | $2d$ | $d^{2}$ | $2d-1$ | $\frac{d-1}{2}$ | $\frac{3d-1}{2}$
| $d=4m$ | $2d+2$ | $d(d+1)$ | $2d+1$ | $\frac{d}{2}$ | $\frac{d}{2}$
IQ($d$) | $d=4m+3$ | $2d+2$ | $d(d+1)$ | $2d+1$ | $\frac{d-1}{2}$ | $\frac{3d+1}{2}$
|  $q$ even | $q^{2}+q+1$ | $\frac{q(q+1)^{2}}{2}$ | $q(q+1)$ | $\frac{q}{2}$ | $\frac{q(q+1)}{2}$
$ER_{q}$ |  $q$ odd | $q^{2}+q+1$ | $\frac{q(q+1)^{2}}{2}$ | $q(q+1)$ | $\frac{q+1}{2}$ | $0$
Table 4. This table gives parameters and several statistics on the common
factor graphs we use throughout this paper. In particular, it counts $t$, the
theoretical upper bound on the number of edge-disjoint spanning trees in the
graph, by dividing the number of edges by the edges in a spanning tree, and
counts $r$, the edges remaining that are not part of these trees.

###  B.1. C(a), a Cayley Graph

The parameter $a$ may be $4k+1$, $4k$ or $4k-1$. In each of these cases, $t=k$
and $r=k$.

####  B.1.1. C($4k+1$) = $QR(4k+1)$ : the Paley Graph

The Paley graph of prime power order $q=4k+1$ has $q$ vertices and
$\frac{q(q-1)}{4}$ edges. Each spanning tree has $q-1$ edges, so the maximum
number of EDSTs in a Paley graph is

$t=\left\lfloor\frac{q(q-1)}{4(q-1)}\right\rfloor=\frac{q-1}{4}=k.$

By (Alspach et al., 2012), a Paley graph may be decomposed into Hamiltonian
cycles, so the bound is attained. The number of remaining non-tree edges is

$r=\frac{q(q-1)}{4}-\frac{(q-1)^{2}}{4}=\frac{q-1}{4}=k.$

####  B.1.2. C($4k$)

The McKay-Miller-Širáň supernode of prime power order $q=4k$ has $q$ vertices
and $\frac{q^{2}}{4}$ edges. Each spanning tree has $q-1$ edges, so the
maximum number of EDSTs in this supernode graph is

$t=\left\lfloor\frac{q^{2}}{4(q-1)}\right\rfloor=\frac{q}{4}=k.$

The number of remaining non-tree edges is

$r=\frac{q^{2}}{4}-\frac{q}{4}(q-1)=\frac{q}{4}=k.$

####  B.1.3. C($4k-1$) : an MMS Supernode

The McKay-Miller-Širáň supernode of prime power order $q=4k-1$ has $q$
vertices and $\frac{q(q+1)}{4}$ edges. Each spanning tree has $q-1$ edges, so
the maximum number of EDSTs in this supernode graph is

$t=\left\lfloor\frac{q(q+1)}{4(q-1)}\right\rfloor=\frac{q+1}{4}=k.$

The number of remaining non-tree edges is

$r=\frac{q(q+1)}{4}-\frac{q+1}{4}\cdot(q-1)=\frac{q+1}{4}=k.$

###  B.2. $K_{q,q}$ : the Bipartite Graph

The bipartite $(q,q)$ graph, where $q>2$ is a prime power, has $2q$ vertices
and $q^{2}$ edges.

Each spanning tree has $2q-1$ edges, so the maximum number of EDSTs in a Paley
graph is

$t=\left\lfloor\frac{q^{2}}{2q-1}\right\rfloor=\begin{cases*}\frac{q-1}{2}=2k&if
$q=4k+1,$\\\ \frac{q}{2}=2k&if $q=4k,$\\\ \frac{q-1}{2}=2k-1&if
$q=4k-1.$\end{cases*}$

The actual number of EDSTs of $K_{q,q}$ was shown to be
$\left\lfloor\frac{q^{2}}{2q-1}\right\rfloor$ by Li et al. in (Li et al.,
2010), so the upper bound is met. The number of remaining non-tree edges is

$r=q^{2}-t\cdot(2q-1)=\begin{cases*}\frac{3q-1}{2}=6k+1&if $q=4k+1,$\\\
\frac{q}{2}=2k&if $q=4k,$\\\ \frac{3q-1}{2}=6k-2&if $q=4k-1.$\end{cases*}$

###  B.3. $H_{q}$, the McKay-Miller-Širáň Graph

$H_{q}$ is not only a factor graph for Bundlefly, but is a star product in its
own right. It is discussed below in the Slim Fly Section C.1. In that section,
these identities are derived: the maximum possible number of spanning trees
$t$ in $H_{q}$ is

$t=\begin{cases*}3k&if $q=4k+1,$\\\ 3k&if $q=4k,$\\\ 3k-1&if
$q=4k-1.$\end{cases*}$

and the number of remaining edges $r$ is

$r=\begin{cases*}q^{2}+3k&if $q=4k+1,$\\\ 3k&if $q=4k,$\\\ q^{2}+3k-1&if
$q=4k-1.$\end{cases*}$

###  B.4. $K_{m}$ : the Complete Graph on $m$ Vertices

The complete graph on $m$ vertices has $m$ vertices and $\frac{m(m-1)}{2}$
edges. Each spanning tree has $m-1$ edges, so the maximum number of EDSTs in a
Paley graph is

$t=\left\lfloor\frac{m(m-1)}{2(m-1)}\right\rfloor=\left\lfloor\frac{m}{2}\right\rfloor=\begin{cases*}\frac{m}{2}&if
$m$ is even,\\\ \frac{m-1}{2}&if $m$ is odd.\end{cases*}$

The the number of remaining non-tree edges is

$r=\frac{m(m-1)}{2}-t(m-1)=\begin{cases*}\ 0&if $m$ is even,\\\
\frac{m-1}{2}&if $m$ is odd.\end{cases*}$

###  B.5. $BDF(d)$: the Bermond-Delorme-Farhi Graph (Bermond et al., 1982)

The Bermond-Delorme-Farhi (BDF) graph of degree $d$ has $2d$ vertices and
$d^{2}$ edges (Bermond et al., 1982). Each spanning tree has $2d-1$ edges, so
the maximum number of EDSTs in a BDF graph is

$t=\left\lfloor\frac{d^{2}}{(2d-1)}\right\rfloor=\left\lfloor\frac{d}{2}\right\rfloor=\begin{cases*}\frac{d}{2}=m&if
$d=2m$,\\\ \frac{d-1}{2}=m&if $d=2m+1$.\end{cases*}$

The number of remaining non-tree edges is

$r=d^{2}-t(2d-1)=\begin{cases*}\frac{d}{2}=m&if $d=2m$,\\\
\frac{3d-1}{2}=3m+1&if $d=2m+1$.\end{cases*}$

###  B.6. $IQ(d)$: the Inductive-Quad Graph (Lakhotia et al., 2023b)

The Inductive-Quad graph of degree $d=4m\text{ or }d=4m+3$ has $2d+2$ vertices
and $d(d+1)$ edges (Lakhotia et al., 2023b). Each spanning tree has $2d+1$
edges, so the maximum number of EDSTs in an Inductive-Quad graph is

$t=\left\lfloor\frac{d(d+1)}{(2d+1)}\right\rfloor=\left\lfloor\frac{d}{2}\right\rfloor=\begin{cases*}\frac{d}{2}=2m&if
$d=4m$,\\\ \frac{d-1}{2}=2m+1&if $d=4m+3$.\end{cases*}$

The number of remaining non-tree edges is

$r=d(d-1)-t(2d+1)=\begin{cases*}\frac{d}{2}=2m&if $d=4m$,\\\
\frac{3d+1}{2}=6m+5&if $d=4m+3$.\end{cases*}$

###  B.7. $ER_{q}$: the Erdős-Rényi Polarity Graph (Erdős and Rényi, 1962;
Brown, 1966)

ERq, with $q$ a prime power (Erdős and Rényi, 1962; Brown, 1966), has
$q^{2}+q+1$ vertices and $\frac{q(q+1)^{2}}{2}$ edges. Each spanning tree has
$q(q+1)$ edges, so the maximum number of EDSTs in ERq is

$t=\left\lfloor\frac{q+1}{2}\right\rfloor=\begin{cases*}\frac{q}{2}=\ell&if
$q=2\ell$,\\\ \frac{q+1}{2}=\ell+1&if $q=2\ell+1$.\end{cases*}$

This theoretical bound is attained up to $q=128$ with edge-disjoint
Hamiltonian paths, shown with a construction in (Lakhotia et al., 2023a). We
conjecture that this bound is always attained.

The total number of remaining non-tree edges is

$r=\frac{q(q+1)^{2}}{2}-tq(q+1)=\begin{cases*}\frac{q(q+1)}{2}=\ell(2\ell+1)&if
$q=2\ell$,\\\ \ 0&if $q=2\ell+1$.\end{cases*}$

##  Appendix C Combinatorial Calculations: Star Product Graphs/Networks

In this section, we calculate the upper bounds of the number of spanning trees
on a given graph, and check to see if the calculations in Theorems 4.5.2,
4.5.1 and 4.3.1 meet these upper bounds. In most cases, they do. A summary of
the results is given in Table 3.

To do this, we solve for

$\left\lfloor\frac{\text{total edges}}{\text{spanning tree
edges}}\right\rfloor=\left\lfloor\frac{\text{total edges}}{\text{vertices
}-1}\right\rfloor.$

###  C.1. Slim Fly

Slim Fly is the McKay-Miller-Širáň graph $H_{q}$ (McKay et al., 1998; Hafner,
2004): the star product $K_{q,q}*\text{C}(q)$. The supernode C($q$) is the
Paley graph $QR(q)$ when $q=4k+1$, and is the $H_{q}$ supernode discussed in
(Hafner, 2004) when $q=4k$ or $q=4k-1$. $H_{q}$ has $2q^{2}$ vertices, and
each spanning tree has $2q^{2}-1$ edges.
There are three cases:
_Case 1: $q=4k+1$._
The number of edges $n$ in a supernode is

$n=\frac{q(q-1)}{4}.$

The total number of edges $e$ is

$e=q^{3}+2q\cdot n=q^{3}+2q\cdot\frac{q(q-1)}{4}=\frac{q^{2}(3q-1)}{2}.$

By Lemma A.0.1, the maximum number $t$ of EDSTs is

$\displaystyle
t=\left\lfloor\frac{q^{2}(3q-1)}{2\cdot(2q^{2}-1)}\right\rfloor$
$\displaystyle=\left\lfloor\frac{3q-1}{4}+\frac{3q-1}{4(2q^{2}-1)}\right\rfloor$
$\displaystyle=\left\lfloor\frac{6k+1}{2}+\frac{6k+1}{2(2q^{2}-1)}\right\rfloor$
$\displaystyle=3k.$

The number $r$ of remaining non-tree edges is

$r=e-t\cdot(2q^{2}-1)=\frac{q^{2}(3q-1)}{2}-3k(2q^{2}-1)=\frac{3q-1}{4}=q^{2}+3k.$

_Case 2: $q=4k$._
The number of edges $n$ in a supernode is

$n=\frac{q^{2}}{4}.$

The total number of edges $e$ is

$e=q^{3}+2q\cdot n=q^{3}+2q\cdot\frac{q^{2}}{4}=\frac{3q^{3}}{2}.$

By Lemma A.0.1, the maximum number $t$ of EDSTs is

$t=\left\lfloor\frac{3q^{3}}{4(2q^{2}-1)}\right\rfloor=\left\lfloor\frac{3q}{4}+\frac{3q}{4(2q^{2}-1)}\right\rfloor=3k.$

The number $r$ of remaining non-tree edges is

$r=e-t\cdot(2q^{2}-1)=\frac{3q^{3}}{2}-3k(2q^{2}-1)=\frac{3q}{4}=3k.$

_Case 3: $q=4k-1$._
The number of edges $n$ in a supernode is

$n=\frac{q(q+1)}{4}.$

The total number of edges $e$ is

$e=q^{3}+2q\cdot n=q^{3}+2q\cdot\frac{q(q+1)}{4}=\frac{q^{2}(3q+1)}{2}.$

By Lemma A.0.1, the maximum number $t$ of EDSTs is

$t=\left\lfloor\frac{e}{2q^{2}-1}\right\rfloor=\left\lfloor\frac{q^{2}(3q+1)}{2\cdot(2q^{2}-1)}\right\rfloor=\left\lfloor\frac{3q+1}{4}+\frac{3q+1}{4(2q^{2}-1)}\right\rfloor=3k-1.$

The number $r$ of remaining non-tree edges is

$r=e-t\cdot(2q^{2}-1)=\frac{q^{2}(3q+1)}{2}-(3k-1)(2q^{2}-1)=q^{2}+3k-1.$

In summary, the maximum possible number of spanning trees $t$ in Slim Fly is

$t=\begin{cases*}3k&if $q=4k+1,$\\\ 3k&if $q=4k,$\\\ 3k-1&if
$q=4k-1.$\end{cases*}$

and the number of remaining edges $r$ is

$r=\begin{cases*}q^{2}+3k&if $q=4k+1,$\\\ 3k&if $q=4k,$\\\ q^{2}+3k-1&if
$q=4k-1.$\end{cases*}$

###  C.2. Bundlefly

Bundlefly is the star product $H_{q}*$Paley($a$), where $q$ is a prime power
and $a$ is a prime power with $a=4k+1$ for some integer $k$. It has
$2q^{2}\cdot a$ vertices, and each spanning tree has $2q^{2}a-1$ edges.

We use Lemma A.0.1 in this section, with $b=2$, $c=q^{2}a$ and

$a=\begin{cases*}\frac{3q-1+4k}{2}&if $q=4\ell+1,$\\\ \frac{3q+4k}{2}&if
$q=4\ell,$\\\ \frac{3q-1+4k}{2}&if $q=4\ell-1,$\end{cases*}$

and note that in each of these cases,

(26)
$\frac{a}{b(bc-1)}=\begin{cases*}\frac{3q-1+4k}{4(2q^{2}a-1)}<\frac{1}{2}&if
$q=4\ell+1$ or $4\ell-1,$\\\ \frac{3q+4k}{4(2q^{2}a-1)}<\frac{1}{2}&if
$q=4\ell$\end{cases*}$

so will not affect the value of the floor function in any of the below cases
when calculating $t$, the maximum number of EDSTs.
There are three cases:
_Case 1: $q=4\ell+1$._
The number of edges $e$ is

$\displaystyle e$ $\displaystyle=\frac{(4k+1)q^{2}(3q-1)}{2}+2q^{2}k(4k+1)$
$\displaystyle=\frac{q^{2}a(3q-1+4k)}{2}.$

By Lemma A.0.1 and Equation (26), the maximum number $t$ of EDSTs is

$\displaystyle
t=\left\lfloor\frac{q^{2}a(3q-1+4k)}{2(2q^{2}a-1)}\right\rfloor$
$\displaystyle=\left\lfloor\frac{3q-1+4k}{4}+\frac{3q-1+4k}{4(2q^{2}a-1)}\right\rfloor$
$\displaystyle=\left\lfloor\frac{12\ell+3-1+4k}{4}+\frac{3q-1+4k}{4(2q^{2}a-1)}\right\rfloor$
$\displaystyle=\left\lfloor
3\ell+k+\frac{1}{2}+\frac{3q-1+4k}{4(2q^{2}a-1)}\right\rfloor$
$\displaystyle=3\ell+k.$

_Case 2: $q=4\ell$._
The number of edges $e$ is

$\displaystyle e$ $\displaystyle=\frac{3(4k+1)q^{3}}{2}+2q^{2}k(4k+1)$
$\displaystyle=\frac{q^{2}a(3q+4k)}{2}.$

By Lemma A.0.1 and Equation (26), the maximum number $t$ of EDSTs is

$\displaystyle t=\left\lfloor\frac{q^{2}a(3q+4k)}{2(2q^{2}a-1)}\right\rfloor$
$\displaystyle=\left\lfloor\frac{3q+4k}{4}+\frac{3q+4k}{4(2q^{2}a-1)}\right\rfloor$
$\displaystyle=\left\lfloor\frac{12\ell+4k}{4}+\frac{3q+4k}{4(2q^{2}a-1)}\right\rfloor$
$\displaystyle=\left\lfloor 3\ell+k+\frac{3q+4k}{4(2q^{2}a-1)}\right\rfloor$
$\displaystyle=3\ell+k.$

_Case 3: $q=4\ell-1$._
The number of edges $e$ is

$\displaystyle e$ $\displaystyle=\frac{(4k+1)q^{2}(3q-1)}{2}+2q^{2}k(4k+1)$
$\displaystyle=\frac{q^{2}a(3q-1+4k)}{2}.$

By Lemma A.0.1 and Equation (26), the maximum number $t$ of EDSTs is

$\displaystyle
t=\left\lfloor\frac{q^{2}a(3q-1+4k)}{2(2q^{2}a-1)}\right\rfloor$
$\displaystyle=\left\lfloor\frac{3q-1+4k}{4}+\frac{3q-1+4k}{4(2q^{2}a-1)}\right\rfloor$
$\displaystyle=\left\lfloor\frac{12\ell-3-1+4k}{4}+\frac{3q-1+4k}{4(2q^{2}a-1)}\right\rfloor$
$\displaystyle=\left\lfloor
3\ell+k-1+\frac{3q-1+4k}{4(2q^{2}a-1)}\right\rfloor$
$\displaystyle=3\ell+k-1.$

###  C.3. PolarStar

PolarStar is the star product $ER_{q}*G^{\prime}$ where $q$ is an even or odd
prime power. $G^{\prime}$ is either the Paley graph QR($a$) with $a=4k+1$, or
the Inductive Quad IQ($d$), with $d$ an integer where $d=4m$ or $d=4m+3$.

_Case 1:_ $G^{\prime}=QR(a)$, the Paley Graph.
In this case, $a=4k+1$. The number of vertices is $(4k+1)(q^{2}+q+1)$. The
number of edges is:

$\displaystyle e$
$\displaystyle=k(4k+1)(q^{2}+q+1)+\frac{q(q+1)^{2}(4k+1)}{2}$
$\displaystyle=\frac{2k(4k+1)(q^{2}+q+1)+q(4k+1)(q+1)^{2}}{2}$
$\displaystyle=\frac{2k(4k+1)(q^{2}+q+1)+q(4k+1)(q^{2}+q+1)+q^{2}(4k+1)}{2}$
$\displaystyle=\frac{(2k+q)(4k+1)(q^{2}+q+1)+q^{2}(4k+1)}{2}$
$\displaystyle=\frac{(2k+q)(4k+1)(q^{2}+q+1)}{2}+\frac{q^{2}(4k+1)}{2}$
$\displaystyle=\frac{(4k+1)[(2k+q)(q^{2}+q+1)+q^{2}]}{2}$

Each spanning tree has $(4k+1)(q^{2}+q+1)-1$ edges, so the maximum number of
spanning trees is

$t=\left\lfloor\frac{(4k+1)((2k+q)(q^{2}+q+1)+q^{2})}{2((4k+1)(q^{2}+q+1)-1)}\right\rfloor$

By Lemma A.0.1,

$t=\left\lfloor\frac{(2k+q)(q^{2}+q+1)+q^{2}}{2(q^{2}+q+1)}+\epsilon\right\rfloor,$

where

$\epsilon=\frac{(2k+q)(q^{2}+q+1)+q^{2}}{2(q^{2}+q+1)((4k+1)(q^{2}+q+1)-1)}.$

So

$\displaystyle t$
$\displaystyle=\left\lfloor\frac{2k+q}{2}+\frac{q^{2}}{2(q^{2}+q+1)}+\epsilon\right\rfloor$
(27) $\displaystyle=k+\left\lfloor\frac{q}{2}+\delta+\epsilon\right\rfloor$

where

$\delta=\frac{q^{2}}{2(q^{2}+q+1)}$

We have that

$\displaystyle\delta+\epsilon$
$\displaystyle=\frac{q^{2}[(4k+1)(q^{2}+q+1)-1]+(2k+q)(q^{2}+q+1)+q^{2}}{2(q^{2}+q+1)[(4k+1)(q^{2}+q+1)-1]}$
$\displaystyle=\frac{(2k+q)(q^{2}+q+1)+q^{2}[(4k+1)(q^{2}+q+1)-1]+q^{2}}{2(q^{2}+q+1)[(4k+1)(q^{2}+q+1)-1]}$
$\displaystyle=\frac{(2k+q)(q^{2}+q+1)+q^{2}(4k+1)(q^{2}+q+1)}{2(q^{2}+q+1)[(4k+1)(q^{2}+q+1)-1]}$
$\displaystyle=\frac{(2k+q)+q^{2}(4k+1)}{2[(4k+1)(q^{2}+q+1)-1]}.$

We note that

$0<\frac{(2k+q)+q^{2}(4k+1)}{2[(4k+1)(q^{2}+q+1)-1]}<\frac{1}{2}$

so

$t=k+\left\lfloor\frac{q}{2}\right\rfloor.$

_Case 2:_ $G^{\prime}=IQ(d)$, the Inductive Quad Graph In this case, $d=4k$ or
$d=4k+3$. The number of vertices is $(q^{2}+q+1)(2d+2)$. The number of edges
is

$\displaystyle e$ $\displaystyle=(q^{2}+q+1)d(d+1)+\frac{(2d+2)q(q+1)^{2}}{2}$
$\displaystyle=(d+1)[d(q^{2}+q+1)+q(q+1)^{2}].$

Each spanning tree has $(q^{2}+q+1)(2d+2)-1$ edges, so the maximum number of
spanning trees is

$\displaystyle t$
$\displaystyle=\left\lfloor\frac{(d+1)[d(q^{2}+q+1)+q(q+1)^{2}]}{2((q^{2}+q+1)(d+1)-1)}\right\rfloor$
$\displaystyle=\left\lfloor\frac{(d+1)[d(q^{2}+q+1)+q(q^{2}+q+1)+q^{2}]}{2((q^{2}+q+1)(d+1)-1)}\right\rfloor$
$\displaystyle=\left\lfloor\frac{d(d+1)(q^{2}+q+1)+q(d+1)(q^{2}+q+1)+(d+1)q^{2}}{2((q^{2}+q+1)(d+1)-1)}\right\rfloor$
$\displaystyle=\left\lfloor\frac{(q+d)(d+1)(q^{2}+q+1)+(d+1)q^{2}}{2((q^{2}+q+1)(d+1)-1)}\right\rfloor$

So

$t=\left\lfloor\alpha+\beta\right\rfloor,$

where

$\alpha=\frac{(q+d)(d+1)(q^{2}+q+1)}{2((q^{2}+q+1)(d+1)-1)}$

and

$\beta=\frac{(d+1)q^{2}}{2((q^{2}+q+1)(d+1)-1)}.$

By Lemma A.0.1, we have that

$\displaystyle\alpha$
$\displaystyle=\frac{(q+d)(d+1)(q^{2}+q+1)}{2((q^{2}+q+1)(d+1)-1)}$
$\displaystyle=\frac{q+d}{2}+\frac{q+d}{2((q^{2}+q+1)(d+1)-1)}.$

So

$t=\left\lfloor\frac{q+d}{2}+\frac{q+d+(d+1)q^{2}}{2((q^{2}+q+1)(d+1)-1)}\right\rfloor.$

We note that

$0<\frac{q+d+(d+1)q^{2}}{2((q^{2}+q+1)(d+1)-1)}<\frac{1}{2},$

so the maximum number $t$ of spanning trees for $q$ odd or even and $d$ odd or
even is $\left\lfloor\frac{q+d}{2}\right\rfloor$.