# Three aspects of the MSTCI problem

Manuel Dubinsky<EMAIL_ADDRESS>César Massri 111Massri was supported
by Instituto de Investigaciones Matemáticas “Luis A. Santaló”, UBA, CONICET,
CABA, Argentina Gabriel Taubin 222Taubin was partially supported by NSF grant
number IIS-1717355. Ingeniería en Informática, Departamento de Tecnología y
Administración, Universidad Nacional de Avellaneda, Argentina  Departamento de
Matemática, Universidad de CAECE, CABA, Argentina  School of Engineering,
Brown University, Providence, RI, USA

###### Abstract

Consider a connected graph $G$ and let $T$ be a spanning tree of $G$. Every
edge $e\in G-T$ induces a cycle in $T\cup\\{e\\}$. The intersection of two
distinct such cycles is the set of edges of $T$ that belong to both cycles.
The MSTCI problem consists in finding a spanning tree that has the least
number of such non-empty intersections and the _instersection number_ is the
number of non-empty intersections of a solution. In this article we consider
three aspects of the problem in a general context (i.e. for arbitrary
connected graphs). The first presents two lower bounds of the intersection
number. The second compares the intersection number of graphs that differ in
one edge. The last is an attempt to generalize a recent result for graphs with
a universal vertex.

###### keywords:

Graphs; Spanning trees; Cycle bases

##  1 Introduction

Let $T$ be a spanning tree of $G$. Every edge $e\in G-T$ induces a cycle in
$T\cup\\{e\\}$. The intersection of two distinct such cycles is the set of
edges of $T$ that belong to both cycles. The MSTCI problem consists in finding
a spanning tree that has the least number of such pairwise non-empty
intersections. The _intersection number_ is the number of non-empty
intersections of a solution.

The theoretical interest and an application of the MSTCI problem are described
in [1]. A conjecture regarding graphs that contain a _universal vertex_ was
recently proved in [2].

The _intersection number_ of $G$ is connected with the sparsity of the
_grammian matrix_ of a cycle matrix. Let $B=(C_{1},\dots,C_{\nu})$ be a cycle
basis with corresponding cycle matrix $\Gamma$. The grammian of $\Gamma$ is
$\hat{\Gamma}=\Gamma^{t}\Gamma$. We will denote $\hat{\Gamma}$ the _cycle
intersection matrix_ of $B$. It is easy to check that the $ij$-entry of
$\hat{\Gamma}$ is 0 if and only if the cycles $C_{i}$ and $C_{j}$ do not
intersect (i.e.: they have no edges in common).

The MSTCI problem corresponds to the particular case of bases that belong to
the strictly fundamental class [3], i.e. bases induced by a spanning tree. The
complexity class of this problem is unknown. In this context it seems natural
to consider the problem of finding a lower bound for the _intersection
number_.

In this article we present a reflection of the MSTCI problem for arbitrary
connected graphs, it is structured as follows. Section 2 sets some notation,
convenient definitions and auxiliary results. Section 3 focuses on the
theoretical and practical interest of two lower bounds of the intersection
number. Section 4 compares the intersection number of graphs that differ in
one edge. Section 5 develops an attempt to generalize a recent result for
graphs with a universal vertex. Section 6 briefly describes the technical
details of the experiments. Finally, Section 7 collects the conclusions.

##  2 Preliminaries

###  2.1 Overview

In the first part of this section we present some of the terms and the
notation used in the article. In the second part we present some lemmas
required in the next section.

###  2.2 Notation

Let $G=(V,E)$ be a graph and $T$ a spanning tree of $G$. The number of
vertices and edges will be $|V|=n$ and $|E|=m$, resp. The number of cycles of
a cycle basis is $\mu=m-n+1$, known as the _cyclomatic number_ of $G$. The
unique path between $u,v\in V$ in the spanning tree $T$, will be denoted
$uTv$. Denote max-deg(G) (resp. max-deg(T)) and min-deg(G) (resp. min-deg(T))
to the maximum and minimum degree of a node of $G$ (resp. $T$)

We will refer to the edges $e\in T$ as _tree-edges_ and to the edges in $G-T$
as _cycle-edges_. Every cycle-edge $e$ induces a cycle in $T\cup\\{e\\}$,
which we will call a _tree-cycle_. We will denote $\cap_{G}(T)$ to the number
of non-empty tree-cycle pairwise intersections w.r.t. $T$, and
$\cap(G)=\cap_{G}(T)$ will be the _intersection number_ of $G$ in the case
where $T$ is a solution of the MSTCI problem.

We shall call _star_ spanning tree to one that has one vertex that connects to
all other vertices, and $K_{n}$ to the complete graph on $n$ nodes. A
_universal vertex_ $u$ of $G$ is a vertex incident to all the other vertices,
i.e. has $max-deg(G)=n-1$. $G$ is a _regular graph_ if all its vertices have
the same degree.

Finally we will refer to the terms _vertex_ and _node_ iterchangeably.

###  2.3 Auxiliary lemmas and definitions

In this section we present some auxiliary lemmas and definitions required in
the next section. In the following, let $G=(V,E)$ be a connected graph and
$T=(V,E^{\prime})$ a spanning tree of $G$.

###### Definition 1

[4] Let $e\in E^{\prime}$ be a tree-edge, consider the two connected
components $T_{1}$ and $T_{2}$ determined by $T-\\{e\\}$, denote the _bond_
$b_{e}$ as the maximal set of edges $(v,w)\in E$ such that $v\in T_{1}$ and
$w\in T_{2}$.

###### Lemma 2

Let $e\in E^{\prime}$ be an edge of $T$ and $b_{e}$ its corresponding bond,
then the edges in $b_{e}-\\{e\\}$ are cycle-edges that determine tree-cycles
that pairwise intersect.

#### Proof

Let $T_{1},T_{2}$ be the two connected components determined by $T-\\{e\\}$,
and let $(v,w)\in b_{e}-\\{e\\}$. By definition $v\in T_{1}$ and $w\in T_{2}$,
then $vTw$ must contain $e$ and $vTw\cup(v,w)$ determines a tree-cycle. This
implies that $(v,w)$ is a cycle-edge and that the edges in $b_{e}-\\{e\\}$
pairwise intersect. $\square$

###### Lemma 3

Let $f=(v,w)\in E-E^{\prime}$ be a cycle-edge, then $f$ belongs to the bonds
corresponding to the edges of $vTw$.

#### Proof

Let $e\in vTw$, consider the two connected components $T_{1},T_{2}$ determined
by $T-\\{e\\}$, clearly $v\in T_{1}$ and $w\in T_{2}$ then by definition $f\in
b_{e}$. $\square$

###### Corollary 4

Every cycle-edge belongs to at least two bonds.

#### Proof

Let $f=(v,w)\in E-E^{\prime}$ be a cycle-edge, as every cycle contains at
least three edges then $vTw$ has at least length two. By the previous lemma
the claim follows. $\square$

Let $B_{T}=\\{b_{e}\\}_{e\in E^{\prime}}$ be the set of bonds w.r.t. $T$, then
-by Lemma 2\- computing the total number of pairs of cycle-edges in $B_{T}$
overestimates $\cap_{G}(T)$

$\sum_{e\in E^{\prime}}\binom{|b_{e}|-1}{2}\geq\cap_{G}(T)$

The overestimation is due to redundant intersections. Note that if the
intersection of two tree-cycles $c_{1},c_{2}$ contains two or more tree-edges
then the corresponding pair of cycle-edges will be contained in more than one
bond. The next lemmas addresses this problem at the cost of incurring in
underestimation.

###### Lemma 5

Let $B_{T}=\\{b_{e}\\}_{e\in E^{\prime}}$ be the set of bonds w.r.t. $T$, then
another set $\bar{B}_{T}=\\{\bar{b}_{e}\\}_{e\in E^{\prime}}$ exists such
that:

  * 1.

$\bar{b}_{e}\subseteq b_{e}$

  * 2.

every edge $e\in E$ belongs to exactly one $\bar{b}_{e}$

#### Proof

As $E$ is finite, then the bonds of $T$ and $B_{T}$ exist and are finite. To
define a set $\bar{B}_{T}$ that meets the conditions, suffices to remove all
but one occurrence of the duplicated edges in the bonds of $B_{T}$.

$\square$

This result motivates the following definition.

###### Definition 6

Let $B_{T}=\\{b_{e}\\}_{e\in E^{\prime}}$ be the set of bonds w.r.t. $T$, then
a _non redundant bond set_ is a set $\bar{B}_{T}=\\{\bar{b}_{e}\\}_{e\in
E^{\prime}}$ such that:

  * 1.

$\bar{b}_{e}\subseteq b_{e}$

  * 2.

every edge $e\in E$ belongs to exactly one $\bar{b}_{e}$

###### Lemma 7

Let $T$ be a solution for the MSTCI problem w.r.t. $G$,
$\bar{B}_{T}=\\{\bar{b}_{e}\\}_{e\in E^{\prime}}$ a non redundant bond set and
$\phi_{e}=|\bar{b}_{e}|-1$ for every $e\in E^{\prime}$, then

  * 1.

$\sum_{e\in E^{\prime}}\binom{\phi_{e}}{2}\leq\cap(G)$

  * 2.

$\mu=\sum_{e\in E^{\prime}}\phi_{e}$

#### Proof

By Lemma 2 the edges in $\bar{b}_{e}-\\{e\\}$ are cycle-edges that pairwise
intersect. There are $\phi_{e}=|\bar{b}_{e}|-1$ cycle-edges in
$\bar{b}_{e}-\\{e\\}$, then $\bar{b}_{e}$ accounts for $\binom{\phi_{e}}{2}$
pairwise intersections. As every edge belongs to exactly one _non redundant
bond_ , every tree-cycle pairwise intersection is counted at most once, then
the first inequality holds. As each bond contains exactly $\phi_{e}$ cycle-
edges and every cycle-edge belongs to exactly one bond, the second equation
follows. $\square$

###### Lemma 8

A quadratic function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ defined as,

$f(x_{1},\dots,x_{n})=\bm{x}^{T}\bm{Q}\bm{x}+\bm{c}^{T}\bm{x}+d$

is strictly convex if and only if $Q$ is positive definite.

#### Proof

First, adding a linear form to a strictly convex function results in a
strictly convex function. Second composing a strictly convex function with a
linear change of coordinates, gives a strictly convex function. Then, we
reduced the proof to the case where $Q$ is diagonal which is trivial.
$\square$

###### Lemma 9

The matrix $M_{n}=\bm{I}+\bm{1}$ where $\bm{I}$ is the $n\times n$ identity
matrix and $\bm{1}$ is the $n\times n$ matrix whose entries are all equal to 1
is positive definite.

#### Proof

By _Sylvester’s criterion_ [5, 7.2.5] a real symmetric matrix is positive
definite if and only if all its leading principal minors are positive, in
other words: the determinant of all its $k\times k$ upper left submatrices is
positive.

Let $M_{k}=\bm{I}+\bm{1}$, where $1\leq k\leq n$ be an upper left submatrix of
$M_{n}$. Note that $M_{k}$ can be expressed as

$M_{k}=\bm{I}+\bm{1}^{k}(\bm{1}^{k})^{T}$

where $1^{k}$ is the $k$-vector whose entries are all equal to 1, and
$\bm{1}^{k}(\bm{1}^{k})^{T}$ is the outer product operation. By the _matrix
determinant lemma_ , which is proved by taking determinant to both sides of
the following equality,

$\begin{pmatrix}\mathbf{I}&0\\\
\mathbf{v}^{\textsf{T}}&1\end{pmatrix}\begin{pmatrix}\mathbf{I}+\mathbf{uv}^{\textsf{T}}&\mathbf{u}\\\
0&1\end{pmatrix}\begin{pmatrix}\mathbf{I}&0\\\
-\mathbf{v}^{\textsf{T}}&1\end{pmatrix}=\begin{pmatrix}\mathbf{I}&\mathbf{u}\\\
0&1+\mathbf{v}^{\textsf{T}}\mathbf{u}\end{pmatrix},$

it follows that the determinant of $M_{k}$ is,

$\det(M_{k})=\det(\bm{I}+\bm{1}^{k}(\bm{1}^{k})^{T})=1+(\bm{1}^{k})^{T}\bm{1}^{k}=1+k>0$

$\square$

The following Theorem clarifies the case of graphs that contain a universal
vertex in the context of the MSTCI problem.

###### Theorem 10

[2] If a graph $G$ admits a star spanning tree $T_{s}$, then

$\cap_{G}(T_{s})\leq\cap_{G}(T)$

for any spanning tree $T$ of $G$.

###### Corollary 11

[2] If a graph $G$ admits a star spanning tree $T_{s}$, then $T_{s}$ is a
solution of the MSTCI problem w.r.t. $G$.

###### Lemma 12

[1] Let $G$ be a graph that admits a star spanning $T_{s}$ then

$\cap(G)=\cap_{G}(T_{s})=\sum_{u\in V-\\{v\\}}\binom{d(u)-1}{2}$

##  3 Lower bounds of the intersection number

###  3.1 Overview

A lower bound of the intersection number seems interesting both in theoretical
and practical terms. It gives an insight in the MSTCI problem and can be
useful for comparing algorithms. In this section we present two of them for an
arbitrary connected graph. In the first part we expose a proof of a lower
bound. In the second, after evaluating its practical interest and based on
experimental evidence we conjecture an improved version.

###  3.2 A proof of a lower bound

###### Theorem 13

Let $G=(V,E)$ be a connected graph, then

$\frac{1}{2}\left(\frac{\mu^{2}}{n-1}-\mu\right)\leq\cap(G)$

#### Proof

Let $T=(V,E^{\prime})$ be a solution of the MSTCI problem w.r.t. $G$. By Lemma
5 it is possible to determine a _non redundant bond set_
$\bar{B}_{T}=\\{\bar{b}_{e}\\}_{e\in E^{\prime}}$. And by Lemma 7 the
following hold:

  1. 1.

$\sum_{e\in E^{\prime}}\binom{\phi_{e}}{2}\leq\cap(G)$

  2. 2.

$\mu=\sum_{e\in E^{\prime}}\phi_{e}$

where $\phi_{e}=|\bar{b}_{e}|-1$ for every $e\in E^{\prime}$. The expression
$\sum_{e\in E^{\prime}}\binom{\phi_{e}}{2}$ can be indentified with a point in
the image of a function $f:\mathbb{R}^{n-1}\rightarrow\mathbb{R}$, defined as

$f(x_{1},\dots,x_{n-1})=\sum_{i=1}^{n-1}\binom{x_{i}}{2}=\sum_{i=1}^{n-1}\frac{x_{i}(x_{i}-1)}{2}.$

In this setting, in order to effectively calculate a lower bound of the
intersection number of $G$, the above expressions lead to the following
quadratic optimization problem [6, §9],

minimize $\displaystyle\quad\sum_{i=1}^{n-1}\binom{x_{i}}{2}$ subject to
$\displaystyle\quad\mu=\sum_{i=1}^{n-1}x_{i}$

This minimization problem can be solved by restricting a degree of freedom of
the objective function, defining
$\bar{f}:\mathbb{R}^{n-2}\rightarrow\mathbb{R}$ as

$\bar{f}(x_{1},\dots,x_{n-2})=f(x_{1},\dots,x_{n-2},\mu-\sum_{i=1}^{n-2}x_{i}).$

The next step is to show that $\bar{f}$ is a strictly convex function and
consequently has a unique global minimum. The function $\bar{f}$ can be
expressed in matrix form as follows,

$\bar{f}(x_{1},\dots,x_{n-2})=\frac{1}{2}\left(\bm{x}^{T}(\bm{I}+\bm{1}^{n-2\times
n-2})\bm{x}-2\mu\bm{x}^{T}\bm{1}^{n-2}+\mu^{2}-\mu\right)$

where $\bm{x}=(x_{1},\dots,x_{n-2})^{T}$, $\bm{I}$ is the $(n-2)\times(n-2)$
identity matrix, $\bm{1}^{n-2\times n-2}$ and $\bm{1}^{n-2}$ are the
$(n-2)\times(n-2)$ matrix and the $n-2$ vector respectively, whose entries are
all equal to 1. By Lemma 8, $\bar{f}$ is strictly convex if and only if
$(\bm{I}+\bm{1}^{n-2\times n-2})$ is positive definite; this fact is proved in
Lemma 9. To calculate the unique minimum of $\bar{f}$ suffices to check where
its gradient vanishes,

$\nabla\bar{f}=(\bm{I}+\bm{1}^{n-2\times n-2})\bm{x}-\mu\bm{1}^{n-2}=0.$

The solution of this linear system is as follows,

$x_{i}=\frac{\mu}{n-1},\quad\forall\ 1\leq i\leq n-2$

and

$x_{n-1}=\mu-\sum_{i=1}^{n-2}x_{i}=\frac{\mu}{n-1}.$

The global minimum is,

$\bar{f}\left(\frac{\mu}{n-1},\dots,\frac{\mu}{n-1}\right)=\frac{1}{2}\left(\frac{\mu^{2}}{n-1}-\mu\right).$

Summarizing, the following inequalities hold,

$\frac{1}{2}\left(\frac{\mu^{2}}{n-1}-\mu\right)\leq\sum_{e\in
E^{\prime}}\binom{\phi_{e}}{2}\leq\cap(G)$

and the global minimum of $\bar{f}$ is a lower bound of the intersection
number of $G$ as claimed. $\square$

In what follows we will refer to the lower bound as

$l_{n,m}:=\frac{1}{2}\left(\frac{\mu^{2}}{n-1}-\mu\right)$

The lower bound can be further improved to a strict inequality, as follows.

###### Lemma 14

Let $G=(V,E)$ be a connected graph where $\mu>0$ then

$l_{n,m}<\cap(G)$

#### Proof

As in the previous proof, let $T=(V,E^{\prime})$ be a solution of the MSTCI
problem w.r.t. $G$, $\bar{B}_{T}=\\{\bar{b}_{e}\\}_{e\in E^{\prime}}$ a _non
redundant bond set_ , and
$\bar{f}(x_{1},\dots,x_{n-2})=f(x_{1},\dots,x_{n-2},\mu-\sum_{i=1}^{n-2}x_{i})$,
where $f:\mathbb{R}^{n-1}\rightarrow\mathbb{R}$ is defined as,

$f(x_{1},\dots,x_{n-1})=\sum_{i=1}^{n-1}\binom{x_{i}}{2}.$

By Theorem 13 the following inequalities hold,

$l_{n,m}=\frac{1}{2}\left(\frac{\mu^{2}}{n-1}-\mu\right)\leq\sum_{e\in
E^{\prime}}\binom{\phi_{e}}{2}\leq\cap(G)$

where $\phi_{e}=|\bar{b}_{e}|-1$ for every $e\in E^{\prime}$, and the
expression in the left is the unique global minimum of $\bar{f}$ which occurs
at,

$x_{i}=\frac{\mu}{n-1}\quad\forall\ 1\leq i\leq n-2$

The previous proof also implies that,

$x_{n-1}=\mu-\sum_{i=1}^{n-2}x_{i}=\frac{\mu}{n-1}$

Suppose that equality holds,

$\frac{1}{2}\left(\frac{\mu^{2}}{n-1}-\mu\right)=\sum_{e\in
E^{\prime}}\binom{\phi_{e}}{2}=\cap(G).$

Since $\bar{B}_{T}$ is a _non redundant bond set_ , then
$\phi_{e}=|\bar{b}_{e}|-1$ is a non negative integer number for every $e\in
E^{\prime}$, this implies that the first equality can occur if and only if

$\phi_{e}=x_{i}=\frac{\mu}{n-1},\quad\forall\ 1\leq i\leq n-1,e\in
E^{\prime}.$

This in turn implies that $n-1$ divides $\mu$. Under this assumption and that
$\mu>0$ then the elements of $\bar{B}_{T}$ mutually differ in
$\phi_{e}=\mu/(n-1)\geq 1$ cycle-edges. Consider the second equality,

$\sum_{e\in E^{\prime}}\binom{\phi_{e}}{2}=\cap(G)$

By Lemma 5 and Lemma 7, for every cycle-edge the left expression in the
equation only accounts (at most) for the cycle intersections restricted to
only one bond of $B_{T}$ to which it belongs. Since by corollary 4 every
cycle-edge belongs to at least two bonds, and these bonds mutually differ in
(at least) $\phi_{e}=\mu/(n-1)\geq 1$ cycle-edges, we conclude that,

$\sum_{e\in E^{\prime}}\binom{\phi_{e}}{2}<\cap(G)$

$\square$

###  3.3 Evaluation

In this part we clarify some properties of $l_{n,m}$.

In order to have practical meaning $l_{n,m}$ must be a positive integer. This
is expressed in the following lemma.

###### Lemma 15

Let $G$ be a connected graph such that $\mu>0$ and $l_{n,m}>0$ then
$m>2(n-1)$.

#### Proof

The above hypothesis implies,

$l_{n,m}=\frac{1}{2}\left(\frac{\mu^{2}}{n-1}-\mu\right)>0\iff\mu^{2}>(n-1)\mu\iff\mu=m-(n-1)>(n-1)\iff
m>2(n-1).$

$\square$

An interpretation of this fact is the following: as Theorem 13 suggests an
equidistribution of the cycle-edges among the bonds of the _non redundant bond
set_ , having $m\leq 2(n-1)$ would lead to a situation in which each bond
contains -at most- one cycle-edge and consequently no tree-cycle
intersections.

In line with the previous result, the next lemma presents an upper bound
condition on $m$ based on Theorem 10.

###### Lemma 16

Let $G=(V,E)$ be a connected graph such that $m>n(n-2)/2$ then $G$ contains a
universal vertex.

#### Proof

Note that if we fix the number of the nodes $|V|=n$, the graph with maximum
number of edges and without a universal vertex is a graph in which at most
every node has degree $n-2$. Then

$m=\frac{1}{2}\sum_{v\in V}d(v)=\frac{n(n-2)}{2}$

$\square$

###### Corollary 17

Let $G=(V,E)$ be a connected graph such that $m>n(n-2)/2$ then $G$ contains a
star spanning tree $T_{s}$ which is a solution of the MSTCI problem and

$\cap(G)=\cap_{G}(T_{s})=\sum_{u\in V-\\{v\\}}\binom{d(u)-1}{2}$

#### Proof

The proof follows immediately by direct application of the previous lemma,
Corollary 11 and Lemma 12. $\square$

The previous results show that $l_{n,m}$ has practical interest in the cases
where $2(n-1)<m\leq n(n-2)/2$.

The next lemma focuses on the quality of $l_{n,m}$ in the sense that
quantifies its underestimation in a particular family of graphs.

###### Lemma 18

Let $G=(V,E)$ be a graph that contains a universal vertex $u\in V$ such that
the subgraph $G-\\{u\\}$ is $k$-regular with $k\geq 4$ then

$\frac{1}{8}\leq\frac{l_{n,m}}{\cap(G)}\leq\frac{1}{4}$

#### Proof

As $d(v)=k$ $\forall v\in V-\\{u\\}$, and the star spanning tree is a solution
of the MSTCI problem then acoording to the intersection number formula,

$\cap(G)=\sum_{v\in V-\\{u\\}}\binom{d(u)-1}{2}=\sum_{v\in
V-\\{u\\}}\binom{k-1}{2}=\frac{(n-1)(k-1)(k-2)}{2}$

Taking into account that,

$m=\frac{1}{2}\sum_{v\in
V}d(v)=\frac{1}{2}\left((n-1)+(n-1)k\right)=\frac{(n-1)(k+1)}{2}$

Then,

$\mu=m-(n-1)=\frac{(n-1)(k+1)}{2}-(n-1)=\frac{(n-1)(k-1)}{2}$

Next we analyze the $l_{n,m}$,

$l_{n,m}=\frac{1}{2}\left(\frac{\mu^{2}}{n-1}-\mu\right)=\frac{(n-1)(k-1)(k-3)}{8}$

and finally we express the quotient,

$\frac{\frac{1}{2}(\frac{\mu^{2}}{n-1}-\mu)}{\cap(G)}=\frac{k-3}{4(k-2)}$

This implies that when $k=4$ and $k\rightarrow\infty$ the lower and upper
bounds are met. $\square$

This last result expresses two facts: 1) the underestimation of $l_{n,m}$ can
be considerable and 2) $l_{n,m}$ seems to perform better in dense graphs. In
the next subsection we will confirm this in the case of small connected
graphs. As the quotient considered in the previous lemma will be referenced
below, we will denote it,

$r_{G}:=\frac{l_{n,m}}{\cap(G)}$

###  3.4 Experimental analysis

In this part we confirm -in line with the previous subsection- that, although
$l_{n,m}$ is interesting from a theoretical perspective, it considerably
underestimates the intersection number. We designed an experiment that
exhaustively analyzed the set of 8-node connected graphs. Figure 1 expresses
the results that can be summarized as follows,

  * 1.

$l_{n,m}$ is at most $\frac{1}{5}\cap(G)$.

  * 2.

minimum $\cap(G)$ (red line) is increasing -this will be related with a
conjectural result in the next subsection.

  * 3.

maximum $\cap(G)$ (blue line) is not increasing; in particular is decreasing
for $m=24$ this is precisely the set of graphs that contains the “last” graph
without a universal vertex (see Lemma 16). In the next section we will see
that this densest graph without a universal vertex achieves the maximum
$\cap(G)$ for $m=24$.

  * 4.

$K_{8}$ has maximum intersection number; it seems reasonable to consider that
$K_{n}$ has maximum intersection number for $n$-node connected graphs.

Figure 1: $8$-node connected graphs maximum $\cap(G)$, minimum $\cap(G)$, mean
$\cap(G)$ and $l_{n,m}$ interpolating lines (left); mean/standard deviation
$r_{G}$ (right).

Important remark: recall that the intersection number is the number of
pairwise intersections of a solution of the MSTCI problem. So a graph with
maximum $\cap(G)$ for a fixed $m$ is a graph such that its intersection number
is greater than or equal to the intersection number of any other graph of $m$
nodes. This should not be confused with the number of pairwise intersections
of the problem of finding a spanning tree that maximizes the number of
pairwise intersections.

###  3.5 A conjectural lower bound

In this part we conjecture an improved lower bound based on experimental
evidence.

First we focus on graphs $G=(V,E)$ with a universal vertex $u\in V$. Recall
from Theorem 10 that the star spanning tree $T_{s}$ is a solution of the MSTCI
problem. Note that the sum of the degrees of the subgraph
$G^{\prime}=G-\\{u\\}$ verify,

$\sum_{v\in G^{\prime}}d(v)=2\mu$

The following equivalent definitions refer to those graphs with a universal
vertex that minimize the intersection number for a fixed number of vertices
and edges. The interpretation is simply the equidistribution of the total
degree among the remaining $n-1$ vertices.

###### Definition 19

Let $G=(V,E)$ be a graph with a universal vertex $u\in V$ and $2\mu=q(n-1)+r$
the integer division of $2\mu$ and $n-1$, we shall say that $G$ is _$\mu$
-regular_ if the degree of every node $v\in V-\\{u\\}$ is $q+1$ or $q+2$.

###### Definition 20

Let $G=(V,E)$ be a graph with a universal vertex $u\in V$ and $2\mu=q(n-1)+r$
the integer division of $2\mu$ and $n-1$, we shall say that $G$ is _$\mu$
-regular_ if -except for $u$\- has exactly $n-1-r$ nodes with degree $q+1$ and
$r$ nodes with degree $q+2$.

It is straightforward to check the equivalence based on the uniqueness of $q$
and $r$. Note that for every $|V|=n$ and $|E|=m$ there are $\mu$-regular
graphs; the proof is also straightforward by induction on $\mu$. The following
lemma shows that $\mu$-regular graphs minimize the intersection number of
graphs with a universal vertex.

###### Lemma 21

Let $G=(V_{G},E_{G})$ be a $\mu-regular$ graph and $H=(V_{H},E_{H})$ be a non
$\mu-regular$ graph with a universal vertex such that $|V_{G}|=|V_{H}|=n$ and
$|E_{G}|=|E_{H}|=m$, then

$\cap(G)<\cap(H)$

#### Proof

Suppose on the contrary that $\cap(H)\leq\cap(G)$. Let $u_{H}$ be a universal
vertex of $H$. And -without loss of generality- let $H$ has minimum
intersection number; more precisely let $J=(V_{J},E_{J})$ be a graph with a
universal vertex such that $|V_{J}|=n$ and $|E_{J}|=m$ then the following
holds,

$\cap(H)\leq\cap(J)$

By definition as $H$ is not $\mu$-regular then a node with maximum degree and
a node with minimum degree $v_{max},v_{min}\in V_{H}-\\{u\\}$ satisfy that
$deg_{H}(v_{max})-deg_{H}(v_{min})>=2$. Let $(v_{max},w)\in E_{H}$ be and edge
such that $w\in V_{H}$ is not a neighbor of $v_{min}$. Consider the graph
$H^{\prime}=(V_{H},E_{H}-\\{(v_{max},w)\\}\cup\\{(v_{min},w)\\})$. According
to the hypothesis on $H$ and the formula presented in Lemma 12 the following
holds,

$\cap(H)=\sum_{v\in V_{H}-\\{u\\}}\binom{d_{H}(v)-1}{2}\leq\sum_{v\in
V_{H}-\\{u\\}}\binom{d_{H^{\prime}}(v)-1}{2}=\cap(H^{\prime})$

As the degrees of all the nodes except for $v_{max}$ and $v_{min}$ coincide in
$H$ and $H^{\prime}$, the above inequality implies that,

$\binom{d_{H}(v_{max})-1}{2}+\binom{d_{H}(v_{min})-1}{2}\leq\binom{d_{H^{\prime}}(v_{max})-1}{2}+\binom{d_{H^{\prime}}(v_{min})-1}{2}$

Let $deg_{H}(v_{min})-1=k$ and $deg_{H}(v_{max})-1=k+t$, rewriting the
inequality we have,

$\binom{k+t}{2}+\binom{k}{2}\leq\binom{k+t-1}{2}+\binom{k+1}{2}$

Expanding the binomials,

$\frac{1}{2}[(k+t)(k+t-1)+k(k-1)]\leq\frac{1}{2}[(k+t-1)(k+t-2)+(k+1)k]$

Which implies,

$(k+t-1)-k\leq 0\implies t\leq 1\implies deg_{H}(v_{max})-deg_{H}(v_{min})\leq
1$

This contradicts the hypothesis on $H$ and consequently proves the lemma.
$\square$

Considering the general case of connected graphs -in an attempt to improve
$l_{n,m}$\- we decided to analyze those graphs that minimize the intersection
number for each fixed $n$ and $m$. The experiment consisted in exhaustively
checking the set of $7$ and $8$-node connected graphs. The interesting result
was that in this general setting, $\mu$-regular graphs also minimize the
intersection number; although not exclusively: in some cases there are other
graphs -without a universal vertex- that achieve the minimum intersection
number. We validated this fact by considering a sample of 1000 randomly
generated (by a uniform distribution) $9$-node connected graphs. This
evaluation resulted positive in all cases, and consequently enables to
formulate the following conjecture on a firm basis,

###### Conjecture 22

Let $G=(V_{G},E_{G})$ be a $\mu-regular$ graph and $H=(V_{H},E_{H})$ be a
connected graph such that $|V_{G}|=|V_{H}|=n$ and $|E_{G}|=|E_{H}|=m$, then

$\cap(G)\leq\cap(H)$

Based on the intersection number formula of Lemma 12, this conjecture implies
the following improved -and tight- lower bound of the intersection number.

###### Corollary 23

Let $G=(V,E)$ be a connected graph and $2\mu=q(n-1)+r$ the integer division of
$2\mu$ and $n-1$, then

$\bar{l}_{n,m}:=(n-1-r)\binom{q}{2}+r\binom{q+1}{2}=(n-1)\binom{q}{2}+q\
r\leq\cap(G)$

###  3.6 Comparison between $l_{n,m}$ and $\bar{l}_{n,m}$

The following lemma expresses an improvement of $\bar{l}_{n,m}$ with respect
to $l_{n,m}$.

###### Lemma 24

Let $m>2(n-1)$ then,

$\bar{l}_{n,m}>2\ l_{n,m}$

#### Proof

The definition of $\mu$-regular graphs implies the following,

$\frac{2\mu-r}{n-1}=q$

Substituting this expression in the definition of $\bar{l}_{n,m}$ we have,

$\bar{l}_{n,m}=(n-1)\binom{q}{2}+q\ r=(n-1)\frac{q\ (q-1)}{2}+q\ r\implies$

$\bar{l}_{n,m}=\frac{(n-1)}{2}\left[\left(\frac{2\
\mu-r}{n-1}\right)^{2}-\frac{2\ \mu-r}{n-1}\right]+r\ \frac{2\ \mu-r}{n-1}$

Consider the quotient,

$\frac{\bar{l}_{n,m}}{l_{n,m}}=\frac{\bar{l}_{n,m}}{\frac{1}{2}\left(\frac{\mu^{2}}{n-1}-\mu\right)}>\frac{\bar{l}_{n,m}}{\frac{1}{2}\left(\frac{\mu^{2}}{n-1}\right)}=\frac{2(n-1)\
\bar{l}_{n,m}}{\mu^{2}}=\frac{1}{\mu^{2}}\left[(2\mu-r)^{2}-(n-1)(2\mu-r)+2r(2\mu-r)\right]=$

$\frac{1}{\mu^{2}}\left[4\mu^{2}-4r\mu+r^{2}-2(n-1)\mu+r(n-1)+4r\mu-2r^{2}\right]=\frac{1}{\mu^{2}}\left[4\mu^{2}-r^{2}-2(n-1)\mu+r(n-1)\right]=$

$4-\frac{r^{2}}{\mu^{2}}-\frac{2(n-1)}{\mu}+\frac{r}{\mu^{2}}(n-1)=4-\frac{2(n-1)}{\mu}+\frac{r}{\mu^{2}}(n-1-r)$

As $0\leq r<n-1$ and $m>2(n-1)\implies\mu>(n-1)$ the last term is greater or
equal than zero then,

$\frac{\bar{l}_{n,m}}{l_{n,m}}>4-\frac{2(n-1)}{n-1}=2$

$\square$

Note that $\bar{l}_{n,m}$ has not a lower restriction -as $l_{n,m}$-, meaning
that it can be applied to any connected graph. Figure 2 compares
$\bar{r}_{G}:=\frac{\bar{l}_{n,m}}{\cap(G)}$ and $r_{G}$ based on the
experiment. In practice it seems that there is a better performance
improvement than that of Lemma 24; roughly speaking $\bar{l}_{n,m}$ is at
least $\frac{1}{2}\cap(G)$ while $l_{n,m}$ is at most $\frac{1}{5}\cap(G)$. It
seems that $\bar{l}_{n,m}$ also performs better in dense graphs.

Figure 2: Comparison of mean/standard deviation of $\bar{r}_{G}$ (blue) and
mean/standard deviation of $r_{G}$ (red) over a random sample of size 1000 of
$9$-node connected graphs.

Another possible comparison between $\bar{l}_{n,m}$ and $l_{n,m}$ is the
following: as the graphs of the hypothesis of Lemma 18 are $\mu$-regular with
$r=0$, then $\bar{r}_{G}=1$ and consequently the bound over this family is
tight. This is much better than the performance of $l_{n,m}$ ($r_{G}\leq
1/4$).

##  4 The intersection number of graphs that differ in one edge

We already suggested in the previous section that the intersection number is
not incresasing w.r.t. the number of edges. In an attempt to understand the
MSTCI problem of closely related graphs it seems natural to consider the
question of adding an edge. More specifically, given two connected graphs
$G=(V,E)$ and $G^{\prime}=(V,E\cup\\{e\\})$ such that $e\notin E$, can we
compare their intersection numbers? A first guess indicates that adding an
edge -and consequently a corresponding tree cycle- should increase the
intersection number. In this section we consider the following question,

###### Question 1

Does a connected graph $G=(V,E)$ exist such that for any graph
$G^{\prime}=(V,E\cup\\{e\\})$ ($e\notin E$), $\cap(G^{\prime})<\cap(G)$?

The first part presents a lemma that connects the intersection number of a
graph with some of its subgraphs. The second introduces the definition of
_successor_ and a strict condition for a connected graph to have greater
intersection number than all its successors. The last part shows that in a
relatively small set of graphs the initial guess does not hold.

###  4.1 Intersection number of certain subgraphs

The following important lemma enables comparing the intersection number of a
graph and certain subgraphs,

###### Lemma 25

Let $G=(V,E)$ and $G^{\prime}=(V^{\prime},E^{\prime})$ be connected graphs
such that:

  * 1.

$G^{\prime}$ is a subgraph of $G$.

  * 2.

$T$ is a solution of the MSTCI w.r.t. $G$.

  * 3.

$T^{\prime}=T\cap G^{\prime}$ is a spanning tree of $G^{\prime}$ (where $T\cap
G^{\prime}$ is the intersection considered as subgraphs of $G$).

then $\cap(G^{\prime})\leq\cap(G)$

#### Proof

Note that the edges $e\in E^{\prime}-T^{\prime}$ are cycle-edges that
determine the same tree-cycles w.r.t. $T^{\prime}$ and $T$ in $G^{\prime}$ and
$G$, resp. Consequently the pairwise intersections between those tree-cycles
are the same. Then the following holds,

$\cap(G^{\prime})\leq\cap_{G^{\prime}}(T^{\prime})=\cap_{G}(T)-\sum_{e\in
G-T-G^{\prime}}\cap_{T}(c_{e})=\cap(G)-\sum_{e\in
G-T-G^{\prime}}\cap_{T}(c_{e})\leq\cap(G)$

where $c_{e}$ is the tree-cycle induced by an edge $e$ and $\cap_{T}(c_{e})$
are the cycle pairwise intersection of $c_{e}$. $\square$

###### Corollary 26

Let $G=(V,E)$ be a connected graph with a universal vertex such that $|V|\leq
n$ then $\cap(G)\leq\cap(K_{n})$

#### Proof

Note that the hypothesis of the previous corollary are met: $G$ is a subgraph
of $K_{n}$, by Theorem 10 $T_{s}$ is a solution of the MSTCI problem w.r.t.
$K_{n}$, and $T_{s}\cap G$ is a spanning tree of $G$, then

$\cap(G)\leq\cap(K_{n})$

$\square$

Note: the previous corollary can also be deduced by comparing the
corresponding formulas described in Lemma 12, although the proof would be less
conceptual.

###  4.2 Intersection number of a graph and its successors

In this section we will consider the following two definitions.

###### Definition 27

Let $G=(V,E)$ be a connected graph then a _successor_ of $G$ is another graph
$H=(V,E\cup\\{e\\})$ with $e\notin E$.

And reciprocally,

###### Definition 28

Let $H=(V,E)$ be a connected graph then a _predecessor_ of $H$ is another
connected graph $G=(V,E-\\{e\\})$ for any edge $e\in E$.

Note that $K_{n}$ has no successors and if $G$ is a tree it has no
predecessors.

The following lemma compares the intersection number of a graph with that of
some of its predecessors.

###### Lemma 29

Let $H=(V,E)$ be a connected graph and $T$ a spanning tree that is a solution
of the MSTCI problem, then for every predecessor $G=(V,E-\\{e\\})$ such that
$e\in E-T$ the following holds

$\cap(G)\leq\cap(H)$

#### Proof

Note that as $G$ is a subgraph of $H$ and $T$ is also a spanning tree of $G$
the hypothesis of Lemma 25 are satisfied. Consquently $\cap(G)\leq\cap(H)$.
$\square$

Interesting in its own right is the reciprocal of this lemma described below.

###### Lemma 30

Let $G=(V,E)$ be a connected graph and $H=(V,E\cup\\{e\\})$ a successor such
that $\cap(H)<\cap(G)$ then for every spanning tree $T$ of $H$ that is a
solution of the MSTCI problem, $e\in T$.

Based on the strong restriction imposed by Lemma 30, a natural aspect to
consider is the relation of the intersection numbers of a graph and its
successors. In other words, how frequent is that $\cap(G)>\cap(H)$ for a graph
$G$ and every successor $H$?

In the particular case that $G$ has a universal vertex the following lemma
applies (the proof is identical to that of Corollary 26),

###### Lemma 31

Let $G=(V,E)$ be a connected graph with a universal vertex then for every
successor $H=(V,E\cup\\{e\\})$, the following holds $\cap(G)\leq\cap(H)$.

In the particular case that $m>n(n-2)/2$ the following stronger lemma
expresses that the intersection number is strictly increasing with respect to
the number of edges.

###### Lemma 32

Let $G=(V,E)$ be a connected graph such that $|E|=m>n(n-2)/2$ and $|V|=n\geq
4$, then for every successor $H=(V,E\cup\\{e\\})$, the following holds
$\cap(G)<\cap(H)$.

#### Proof

By Lemma 16, $G$ contains a universal vertex, so the previous lemma guarantees
that $\cap(G)\leq\cap(H)$. To see that the inequality is strict, note that
both $G$ and $H$ admit star spanning trees $T_{s}^{G}$ and $T_{s}^{H}$, resp.,
centered at the same node. So Theorem 10 guarantees that

$\cap(H)=\cap_{H}(T_{s}^{H})=\cap_{G}(T_{s}^{G})+\cap_{T_{s}^{G}}(c_{e})=\cap(G)+\cap_{T_{s}^{G}}(c_{e})$

where $c_{e}$ is the tree-cycle induced by the edge $e=(u,v)$. To see that
$\cap_{T_{s}^{G}}(c_{e})>0$ it is enough to check that $d(u)>1$ or $d(v)>1$ in
$G$. Suppose that both $d(u)=d(v)=1$ in $G$ and that the ramaining edges have
maximum degree: 1) the root of $T_{s}^{G}$ has degree n-1 and 2) the rest of
the vertices have degree (n-3). Summing all,

$m=\frac{1}{2}\sum_{v\in
V}d(v)=\frac{1}{2}[(n-1)+(n-2)(n-3)+2]=\frac{1}{2}[(n-2)^{2}+3]$

By hypothesis $m>n(n-2)/2$, then

$m=\frac{1}{2}[(n-2)^{2}+3]>\frac{1}{2}n(n-2)$

which implies

$(n-2)^{2}+3>n(n-2)\implies-2(n-2)+3>0\implies n<\frac{7}{2}$

$\square$

###  4.3 Experimental analysis

In order to measure the set of graphs that have greater intersection number
than all its successors, we designed an experiment to exhaustively analyze
graphs such that $5\leq|V|\leq 8$. Table LABEL:tab:small_inst describes the
results.

Table 1: Small graphs analysis. $|V|$ | Non-isomorphic graphs |  $\cap(G)>$ all successors
---|---|---
5 | 21 | 0
6 | 112 | 0
7 | 853 | 0
8 | 11117 | 6

Note that the set of graphs with intersection number greater than all its
successors is relatively small. There are six cases for $8$-node graphs. This
rare cases are described in Table LABEL:tab:counterxample_description.
Following are some remarks about its columns,

  * 1.

The graphs are labeled incrementally according to their number of edges.

  * 2.

The number of _Succesors_ of $G_{i}$ is exactly the difference of edges
between $K_{8}$ and $G_{i}$, i.e.: $|E|+Succesors=28$. Some may be isomorphic
and counted many times.

  * 3.

The different intersection numbers of the $Successors$ (in parenthesis in the
last column) are less than the number of $Successors$, this is because: 1) the
graphs induced by two successors may be isomorphic or 2) non-isomorphic graphs
induced by two successors may have the same intersection number.

Table 2: 8-node graph with intersection number greater than all its successors. Graph | $|E|$ | Successors |  $\cap(G)$ (and its successors)
---|---|---|---
$G_{1}$ | 19 | 9 | 46 (44, 45)
$G_{2}$ | 20 | 8 | 54 (52, 53)
$G_{3}$ | 22 | 6 | 60 (59)
$G_{4}$ | 23 | 5 | 69 (66, 68)
$G_{5}$ | 23 | 5 | 69 (66, 67)
$G_{6}$ | 24 | 4 | 82 (75)

Figure 3 depicts these six graphs. Note that $G_{6}$ (at the bottom right) is
the densest graph without a universal vertex, it is the unique $(n-2)$-regular
graph, so all of its successors contain a universal vertex. This graph also
achieves the maximum intersection number for $m=24$ as mentioned in the
previous section.

At the moment it is not clear if this graphs are related, except for the fact
they are all subgraphs of $G_{6}$.

Figure 3: From top left to bottom right, 8-node graphs $G_{1}$, $G_{2}$,
$G_{3}$, $G_{4}$, $G_{5}$, $G_{6}$, with intersection number greater than all
its successors.

##  5 An attempt to generalize Theorem 10

Theorem 10 is the most general tool so far to understand the MSTCI problem. It
would be important for theoretical and practical reasons to generalize it to
an arbitrary graph. In this context we consider the following question,

###### Question 2

Let $G=(V,E)$ be a connected graph, is it true that a spanning tree that is a
solution of the MSTCI problem always exists such that $max-deg(G)=max-deg(T)$?

A positive answer to it would directly imply Theorem 10. In this section we
analyze this problem.

###  5.1 Experimental results

As in the previous section, we exhaustively analyzed graphs such that
$5\leq|V|\leq 8$. Table LABEL:tab:small_inst2 describes the results. Clearly
the implicit assertion of Question 2 is false; the proportion of cases
increases with the number of nodes.

Table 3: Small graphs analysis. $|V|$ | Non-isomorphic graphs |  $max-deg(G)>max-deg(T)$ (for all MSTCI solution $T$)
---|---|---
5 | 21 | 0
6 | 112 | 2
7 | 853 | 47
8 | 11117 | 1189

Figure 4 shows that the set of 8-node connected graphs and the set of cases
for which the implicit assertion of Question 2 does not hold have a similar
distribution with respect to the number of edges. This suggests that the
number of counterexamples is simply proportional and discourages further
analysis.

Figure 4: 8-node connected graph histogram (left) and counterexample histogram
(right).

##  6 Technical details

A brief summary of the technical details of the experiments is the following,

  * 1.

The set of connected graphs for a given number of vertices where generated
with the nauty [7] software.

  * 2.

The graph figures were rendered with graphviz [8].

  * 3.

The programs where coded with the tinygarden java package [9].

  * 4.

The figures were generated with googlecolab [10].

##  7 Conclusion

This article considers the MSTCI problem of arbitrary connected graphs. In
this general setting we focused on three different aspects. The first presents
two lower bounds of the intersection number of a connected graph. The proof of
the first lower bound ($l_{n,m}$) suggests two structural characteristics of
the MSTCI problem, a solution to it should be the “best possible combination”
of the following conditions,

  * 1.

Tree-cycles should have short length so that each cycle-edge belongs to the
least number of bonds.

  * 2.

Cycle-edges should be equidistributed among bonds.

The first condition resembles the fundamental cycle basis problem [3], and the
low-stretch spanning tree problem [11], [12]. This similarities define
interesting directions of research. The second tight lower bound
($\bar{l}_{n,n}$) is presented in a conjectural form (Conjecture 22). It is
based on what we denoted $\mu$-regular graphs. These graphs verify the
previous conditions and consequently reinforce their importance. This last
bound shows that graphs with a universal vertex play a fundamental role, both
because they are well understood cases and they provide examples of minimum
intersection number. It also presents a global picture of the quadratic
surface of the minimum intersection number as a function of the number of
nodes and edges.

The second aspect of the article constitutes a first step towards
understanding the relation of a connected graph $G$ and the set of graphs that
contain one edge more than $G$, which we denoted its _successors_. We showed
that there is a strong restriction for a connected graph to have an
intersection number greater than all of them. Experimental results showed that
those graphs actually exist although they seem to be infrequent. The most
notable example is the $8$-node $6$-regular graph. This fact seems to be
general, and can be expressed in conjectural terms as: for $n$ even the
$(n-2)$-regular graph has intersection number greater than its successor (note
that in this case there is just one). These graphs are the densest without a
universal vertex. They are good examples to investigate this singular
behavior, and more generally they are a good starting point to understand
relevant structural properties.

Theorem 10 is the most important tool so far to understand the MSTCI problem.
It implies that the densest cases are known (Lemma 16) and that the efforts
should concentrate in cases where $m\leq n(n-2)/2$. In the last part of the
article we explore the possibility of a natural generalization of this
theorem. More specifically, we considered the fact that if for every connected
graph $G$ a solution $T$ containing a node of maximal degree should exist, ie.
$max-deg(G)=max-deg(T)$. Experimental results determined a negative answer.
Counterexamples have the same distribution with respect to the number edges
for a fixed number of nodes than the set of connected graphs which indicates
that they are simply proportional and consequently discourages any further
analysis in this direction.

## References

  * Dubinsky et al. [2021] M. Dubinsky, C. Massri, G. Taubin,  Minimum spanning tree cycle intersection problem,  Discrete Applied Mathematics 294 (2021) 152–166. URL: https://doi.org/10.1016/j.dam.2021.01.031. doi:10.1016/j.dam.2021.01.031.
  * Chen and Chao [2022] M.-J. Chen, K.-M. Chao,  Proof of a conjecture about minimum spanning tree cycle intersection,  Discrete Applied Mathematics 321 (2022) 19–23. URL: https://www.sciencedirect.com/science/article/pii/S0166218X22002232. doi:https://doi.org/10.1016/j.dam.2022.06.030.
  * Kavitha et al. [2009] T. Kavitha, C. Liebchen, K. Mehlhorn, D. Michail, R. Rizzi, T. Ueckerdt, K. A. Zweig,  Cycle bases in graphs characterization, algorithms, complexity, and applications,  Computer Science Review 3 (2009) 199–243. URL: https://doi.org/10.1016/j.cosrev.2009.08.001. doi:10.1016/j.cosrev.2009.08.001.
  * Bondy and Murty [2008] J. A. Bondy, U. S. R. Murty, Graph Theory, Springer London, 2008\. URL: https://doi.org/10.1007/978-1-84628-970-5. doi:10.1007/978-1-84628-970-5.
  * Horn and Johnson [2013] R. A. Horn, C. R. Johnson, Matrix analysis, second ed., Cambridge University Press, Cambridge, 2013\.
  * Murty [2010] K. G. Murty, Optimization for decision making, volume 137 of International Series in Operations Research & Management Science, Springer, New York, 2010\. URL: https://doi.org/10.1007/978-1-4419-1291-6. doi:10.1007/978-1-4419-1291-6, linear and quadratic models.
  * McKay and Piperno [2014] B. D. McKay, A. Piperno,  Practical graph isomorphism, II,  Journal of Symbolic Computation 60 (2014) 94–112. URL: https://doi.org/10.1016/j.jsc.2013.09.003. doi:10.1016/j.jsc.2013.09.003.
  * Ellson et al. [2004] J. Ellson, E. R. Gansner, E. Koutsofios, S. C. North, G. Woodhull,  Graphviz and dynagraph static and dynamic graph drawing tools,  in: Graph Drawing Software, Springer Berlin Heidelberg, 2004, pp. 127–148. URL: https://doi.org/10.1007/978-3-642-18638-7_6. doi:10.1007/978-3-642-18638-7\\_6.
  * Dubinsky et al. [2021] M. Dubinsky, C. Massri, G. Taubin,  tinygarden a java package for testing properties of spanning trees,  Software Impacts 9 (2021) 100083. URL: https://doi.org/10.1016/j.simpa.2021.100083. doi:10.1016/j.simpa.2021.100083.
  * Bisong [2019] E. Bisong,  Google colaboratory,  in: Building Machine Learning and Deep Learning Models on Google Cloud Platform, Apress, 2019, pp. 59–64. URL: https://doi.org/10.1007/978-1-4842-4470-8_7. doi:10.1007/978-1-4842-4470-8\\_7.
  * Alon et al. [1995] N. Alon, R. M. Karp, D. Peleg, D. West,  A graph-theoretic game and its application to the k-server problem,  SIAM Journal on Computing 24 (1995) 78–100. URL: https://doi.org/10.1137/s0097539792224474. doi:10.1137/s0097539792224474.
  * Elkin et al. [2005] M. Elkin, Y. Emek, D. A. Spielman, S.-H. Teng,  Lower-stretch spanning trees,  in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, ACM, 2005\. URL: https://doi.org/10.1145/1060590.1060665. doi:10.1145/1060590.1060665.