# The Number of Spanning Trees in the Composition Graphs

Authors: Feng Li
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Using the composition of some existing smaller graphs to construct some large graphs, the number of spanning trees and the Laplacian eigenvalues of such large graphs are also closely related to those of the corresponding smaller ones. By using tools from linear algebra and matrix theory, we establish closed formulae for the number of spanning trees of the composition of two graphs with one of them being an arbitrary complete 3-partite graph and the other being an arbitrary graph. Our results extend some of the previous work, which depend on the structural parameters such as the number of vertices and eigenvalues of the small graphs only.


---

## Body

## 1. Introduction

In reliable network synthesis, given the classΩ
(
n
,
m
) of all connected graphs with n vertices and m edges, it is very important to seek graphs (known as the t-optimal graphs) with the most number of spanning trees, so the number of spanning trees is closely connected to reliable network design [1, 2]. When using a probabilistic graph to model a communication network, the reliability of a network can be expressed as a function of the number of connected spanning subgraphs (spanning trees) of different orders. Thus, the number of spanning trees of a graph describing a network is one of the most natural characteristics for its reliability, and deriving closed formulae of the number of spanning trees for various graphs has attracted the attention of a lot of researchers [3–5].It is well known that the number of spanning trees of some specific family of graphs can be given explicitly, which include the complete graphK
n, the path P
n, the cycle C
n, the wheel W
n, and the Möbius ladders; “almost-complete” graphs, the threshold graphs, and some multicomplete/star related graphs can also be obtained [6–9].Mathematic structures can be properly understood if one has a grasp of their symmetries; it also helps to know whether they can be constructed from smaller constituents, since many large graphs (networks) are usually composed from some existing smaller graphs (networks) through graph operations (say, product [10]). In this paper, we are mainly concerned with the number of spanning trees of the composition of two graphs. Let G
1 and G
2 be two simple graphs;the composition graphs of G
1 and G
2, denoted by G
1
⊙
G
2, are a graph with vertex set V
(
G
1
)
×
V
(
G
2
), and there is an edge between (
u
1
,
u
2
) and (
v
1
,
v
2
) if there is an edge connecting u
1 and v
1 in G
1, or if u
1
=
v
1 and there is an edge connecting u
2 and v
2 in G
2. Sometimes it is also calledlexicographic product. The topological parameters and some properties of such large graphs (networks) are associated strongly with those of the corresponding smaller ones.Since the composition (lexicographic product) of two graphs is noncommutative, for example see Figure1.Figure 1The structure ofK
l
1
,
l
2
,
…
,
l
s
⊙
G is different from the structure of G
⊙
K
l
1
,
l
2
,
…
,
l
s. However, the number of the spanning trees of the composition graphs G
⊙
K
l
1
,
l
2
,
…
,
l
s is got in [11]. In this paper, we enumerate spanning trees of the composition graphs with one of them being an arbitrary complete 3-partite graph K
s
1
,
s
2
,
s
3 and the other an arbitrary graph G. The number of the spanning trees of the composition graphs K
s
1
,
s
2
,
s
3
⊙
G depends only on the number of vertices and eigenvalues of small graphs only.A major open problem which still remains is to devise a technique that would derive close formulae fort
(
G
1
⊙
G
2
) and t
(
G
2
⊙
G
1
), where G
1 and G
2 are arbitrary graphs, or one of them is an arbitrary regular graph. Fiedler [12] gave the eigenvalues of nonnegative symmetric matrices where he obtains the description of the eigenspace of some matrix operations. This actually has been applied for some graph product in [13]. There may be some relations between the techniques used in this note. For more details on the composition graphs and matrix operations the reader is referred to [14–16].


## 2. Preliminaries

We start with fixing some notations. Throughout the paper, letG
=
(
V
,
E
) be a simple graph with vertex set V
=
{
v
1
,
v
2
,
…
,
v
n
} and edge set E
=
{
e
1
,
e
2
,
…
,
e
m
}. Let A
(
G
)
=
(
h
i
j
)
n
×
n be the (
0,1
)-adjacency matrix of G, and let D
(
G
)
=
diag
⁡
(
d
1
,
d
2
,
…
,
d
n
) be the diagonal matrix with d
i being the degree of the ith vertex of G. The Laplacian matrix of G is defined to be L
(
G
)
=
D
(
G
)
-
A
(
G
), and the corresponding characteristic polynomial of L
(
G
) is denoted by P
(
G
,
λ
). Since the matrix L
(
G
) is symmetric, all its eigenvalues are real. We assume without loss of generality that they are arranged in the nondecreasing order; that is, 0
=
λ
1
≤
λ
2
≤
⋯
≤
λ
n. The number of spanning trees of G is denoted by t
(
G
). For other terminologies and notations which are not defined here, the reader is referred to [17].Lemma 1 (see [17, 18]).
Let0
=
λ
1
≤
λ
2
≤
⋯
≤
λ
n be the eigenvalues of the Laplacian matrix of the graph G; then
(1)
∏
i
=
2
n
‍
(
λ
-
λ
i
(
G
)
)
=
|
1
h
12
⋯
h
1
n
1
λ
-
d
2
⋯
h
2
n
⋮
⋮
⋮
1
h
n
2
⋯
λ
-
d
n
|
∶
=
B
(
G
,
λ
)
.It is well known that the number of spanning treest
(
G
) of a given graph G can be calculated through Kirchhoff’s “Matrix-Tree Theorem.” This is one of the first (and most impressive) contributions of spectral theory.Lemma 2 (see [19]).
LetG be graph on n vertices. Let 0
=
λ
1
≤
λ
2
≤
⋯
≤
λ
n denote the eigenvalues of L
(
G
). Then
(2)
t
(
G
)
=
1
n
∏
i
=
2
n
‍
λ
i
(
G
)
.LetJ
0 be the all-zero matrix, and let J
n be the all-one matrix, of order n. Now we give the main results of this paper.Theorem 3.
LetG be a simple graph with n vertices. Let λ
i, i
=
1,2
,
…
,
n, be the Laplacian eigenvalues of L
(
G
) which are arranged in the nondecreasing order. Then, the eigenvalues of L
(
K
s
1
,
s
2
,
s
3
⊙
G
) are 0, {
n
w
}
2, {
n
(
w
-
s
i
)
}
(
s
i
-
1
), and {
λ
k
(
G
)
+
n
(
w
-
s
i
)
}
(
n
-
1
)
s
i, where the exponents denote the multiplicities of the eigenvalues, for i
=
1,2
,
3,  k
=
2,3
,
…
,
n, and w
=
∑
j
=
1
3
s
j.Proof.
LetL
(
G
) be the Laplacian matrix of the graph G. Let u
1
,
u
2
,
…
,
u
s
1
,
…
,
u
s
1
+
s
2
,
…
,
u
w
(
w
=
∑
i
=
1
3
s
i
) be the labels of the graph K
s
1
,
s
2
,
s
3, where u
j
~
u
i if and only if i
∈
A
a and j
∉
A
a, or i
∉
A
a and j
∈
A
a, where A
a
=
{
x
∣
∑
i
=
0
a
-
1
s
i
+
1
≤
x
≤
∑
i
=
0
a
s
i
} (assume that s
0
=
0), for a
=
1,2
,
3. The node (
u
i
,
v
j
) of the graph K
s
1
,
s
2
,
s
3
⊙
G is the lexicographic order among vertex sequences; then we can represent the Laplacian matrix L
(
K
s
1
,
s
2
,
s
3
⊙
G
) in the following block matrix form:
(3)
L
(
K
s
1
,
s
2
,
s
3
⊙
G
)
=
[
D
1
0
⋯
0
0
D
2
⋯
0
⋮
⋮
⋮
0
0
⋯
D
w
]
-
[
A
11
A
12
⋯
A
1
w
A
21
A
22
⋯
A
2
w
⋮
⋮
⋮
A
w
1
A
w
2
⋯
A
w
w
]
,
where the element a
j
l
i
k of the block A
i
k
=
(
a
j
l
i
k
)
n
×
n denotes the adjacency relation of the two nodes (
u
i
,
v
j
) and (
u
k
,
v
l
). By the definition of the composition graphs, (
u
i
,
v
j
)
~
(
u
k
,
v
l
) if and only if u
i
~
u
k; or u
i
=
u
k and v
j
~
v
l. Thus, we have
(4)
a
j
l
i
k
=
{
0
i
≠
k
i
,
k
∈
A
a
1
i
≠
k
otherwise
0
i
=
k
j
=
l
h
j
l
i
=
k
j
≠
l
(
a
=
1,2
,
3
)
.
That is,
(5)
A
i
k
=
{
J
0
i
≠
k
,
i
,
k
∈
A
a
J
n
i
≠
k
otherwise
A
(
G
)
i
=
k
otherwise
(
a
=
1,2
,
3
)
.
Similarly, since the sum of the elements of every row (resp., column) of Laplacian matrix L
(
K
s
1
,
s
2
,
s
3
⊙
G
) is zero, we have
(6)
D
i
=
{
D
(
G
)
+
n
(
w
-
s
1
)
I
n
1
≤
i
≤
s
1
D
(
G
)
+
n
(
w
-
s
2
)
I
n
s
1
+
1
≤
i
≤
s
1
+
s
2
D
(
G
)
+
n
(
w
-
s
3
)
I
n
s
1
+
s
2
+
1
≤
i
≤
s
1
+
s
2
+
s
3
.
Let D
i
=
D
(
s
i
), where D
(
s
i
) is an n
×
n matrix, i
=
1,2
,
…
,
w. Then we get
(7)
L
(
K
s
1
,
s
2
,
s
3
⊙
G
)
=
|
C
1
-
J
s
1
×
s
2
-
J
s
1
×
s
3
-
J
s
2
×
s
1
C
2
-
J
s
2
×
s
3
-
J
s
3
×
s
1
-
J
s
3
×
s
2
C
3
|
w
×
w
,
w
=
∑
i
=
1
3
‍
s
i
,
where J
s
i
×
s
j is an s
i by s
j block matrix with each block being equal to J
n,  i, j
=
1,2
,
3, and
(8)
C
i
=
[
D
(
s
i
)
-
A
(
G
)
0
0
0
D
(
s
i
)
-
A
(
G
)
0
0
0
D
(
s
i
)
-
A
(
G
)
]
s
i
×
s
i
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
i
=
1,2
,
3
.
So the characteristic polynomial of the Laplacian matrix is
(9)
P
(
K
s
1
,
s
2
,
s
3
⊙
G
,
λ
)
=
det
⁡
(
λ
I
p
×
p
-
L
(
K
s
1
,
s
2
,
s
3
⊙
G
)
)
(10)
=
|
B
1
J
s
1
×
s
2
J
s
1
×
s
3
J
s
2
×
s
1
B
2
J
s
2
×
s
3
J
s
3
×
s
1
J
s
3
×
s
2
B
3
|
w
×
w
,
w
=
∑
i
=
1
n
‍
s
i
,
where
(11)
B
i
=
[
λ
(
s
i
)
-
L
(
G
)
0
0
0
λ
(
s
i
)
-
L
(
G
)
0
0
0
λ
(
s
i
)
-
L
(
G
)
]
s
i
×
s
i
,
and λ
(
s
i
)
=
(
λ
-
n
(
w
-
s
i
)
)
I
n, for i
=
1,2
,
3.
In (10), according to the property of the Laplacian matrix, add all the columns to the first column; then every element of the first column is equal to λ. Extract λ; then every element of the first column is equal to 1. Using the notation B
(
G
,
λ
) from Lemma 1, we have
(12)
P
(
K
s
1
,
s
2
,
s
3
⊙
G
,
λ
)
=
det
⁡
(
λ
I
w
×
w
-
L
(
K
s
1
,
s
2
,
s
3
⊙
G
)
)
(13)
=
λ
|
B
*
J
s
1
×
s
2
J
s
1
×
s
3
J
s
2
×
s
1
B
2
J
s
2
×
s
3
J
s
3
×
s
1
J
s
3
×
s
2
B
3
|
w
×
w
,
w
=
∑
i
=
1
3
‍
s
i
,
where
(14)
B
*
=
[
B
(
G
,
λ
-
n
(
w
-
s
1
)
)
0
⋯
0
C
λ
(
s
1
)
-
L
(
G
)
⋯
0
⋮
⋮
⋮
C
0
⋯
λ
(
s
1
)
-
L
(
G
)
]
s
1
×
s
2
C
=
[
1
0
⋯
0
1
0
⋯
0
⋮
⋮
⋮
1
0
⋯
0
]
.
In order to compute the determinant in (13), we start by subtracting the first column from the (
n
s
1
+
1
)th column to the last column, getting
(15)
P
(
K
s
1
,
s
2
,
s
3
⊙
G
,
λ
)
=
λ
|
B
*
0
0
J
s
2
×
s
1
A
2
0
J
s
3
×
s
1
J
s
3
×
s
2
A
3
|
w
×
w
,
w
=
∑
i
=
1
3
‍
s
i
,
where
(16)
A
j
=
[
λ
(
s
j
)
-
L
(
G
)
-
J
n
-
J
n
⋯
-
J
n
-
J
n
λ
(
s
j
)
-
L
(
G
)
-
J
n
⋯
-
J
n
⋮
⋮
⋮
-
J
n
-
J
n
⋯
λ
(
s
j
)
-
L
(
G
)
-
J
n
]
,
s
j
×
s
j
for j
=
2,3.
It follows from (15) that
(17)
P
(
K
s
1
,
s
2
,
s
3
⊙
G
,
λ
)
=
λ
B
(
G
,
λ
-
n
(
w
-
s
1
)
)
×
[
det
⁡
(
(
λ
-
n
(
w
-
s
1
)
)
I
n
-
L
(
G
)
)
]
s
1
-
1
×
F
,
where
(18)
F
=
|
A
2
0
0
A
3
|
(
w
-
s
1
)
×
(
w
-
s
1
)
.
Let H
i
=
det
⁡
(
A
i
), i
=
2,3. According to the property of the determinant, we have
(19)
F
=
H
2
×
H
3
=
∏
i
=
2
3
‍
H
i
,
where
(20)
H
i
=
|
λ
(
s
i
)
-
L
(
G
)
-
J
n
-
J
n
⋯
-
J
n
-
J
n
λ
(
s
i
)
-
L
(
G
)
-
J
n
⋯
-
J
n
⋮
⋮
⋮
-
J
n
-
J
n
⋯
λ
(
s
i
)
-
L
(
G
)
-
J
n
|
s
i
×
s
i
,
for i
=
2,3.
Adding all the columns to the first column and extracting the termλ
-
n
∑
i
=
1
3
s
i, let
(21)
X
=
[
1
h
12
-
1
⋯
h
1
n
-
1
1
λ
-
n
(
w
-
s
i
)
-
d
2
-
1
⋯
h
2
n
-
1
⋮
⋮
⋮
1
h
n
2
-
1
⋯
λ
-
n
(
w
-
s
i
)
-
d
n
-
1
]
n
×
n
,
Y
=
[
1
-
1
⋯
-
1
1
-
1
⋯
-
1
⋮
⋮
⋮
1
-
1
⋯
-
1
]
n
×
n
then
(22)
H
i
=
(
λ
-
n
∑
i
=
1
3
‍
s
i
)
|
X
-
J
n
⋯
-
J
n
Y
Z
⋯
-
J
n
⋮
⋮
⋮
Y
-
J
n
⋯
Z
|
s
i
×
s
i
,
where Z
=
λ
-
n
(
w
-
s
i
)
I
n
-
L
(
G
)
-
J
n, for i
=
2,3.
Adding the first column to all the other columns, we get(23)
H
i
=
(
λ
-
n
w
)
|
B
(
G
,
λ
-
n
(
w
-
s
i
)
)
0
⋯
0
C
Z
+
J
n
⋯
0
⋮
⋮
⋮
C
0
⋯
Z
+
J
n
|
s
i
×
s
i
(24)
=
(
λ
-
n
w
)
·
B
(
G
,
λ
-
n
(
w
-
s
i
)
)
·
[
det
⁡
(
λ
-
n
(
w
-
s
i
)
I
n
-
L
(
G
)
)
]
s
i
-
1
,
for i
=
2,3.
From Lemma1 and the property of the determinant, notice that B
(
G
,
λ
)
=
∏
i
=
2
n
(
λ
-
λ
i
(
G
)
), det
⁡
(
λ
I
n
-
L
(
G
)
)
=
λ
∏
i
=
2
n
(
λ
-
λ
i
(
G
)
); substituting these into equality (24), we get the value of the determinant H
i:
(25)
H
i
=
(
λ
-
n
w
)
·
∏
i
=
2
n
(
λ
-
n
(
w
-
s
i
)
-
λ
i
(
G
)
)
×
[
(
λ
-
n
(
w
-
s
i
)
)
·
∏
i
=
2
n
‍
[
λ
-
n
(
w
-
s
i
)
-
λ
i
(
G
)
]
]
s
i
-
1
for i
=
2,3.
Combining (17), (19), and (25), we obtain
(26)
P
(
K
s
1
,
s
2
,
s
3
⊙
G
,
λ
)
=
λ
(
λ
-
n
w
)
2
∏
i
=
1
n
‍
(
λ
-
n
(
w
-
s
i
)
)
s
i
-
1
×
∏
i
=
1
3
‍
∏
k
=
2
n
‍
[
λ
-
n
(
w
-
s
i
)
-
λ
k
(
G
)
]
s
i
.
Then we get the eigenvalues of K
s
1
,
s
2
,
s
3
⊙
G from above equality immediately. This completes the proof.Theorem 4.
LetG be a graph with Laplacian eigenvalues 0
=
λ
1
≤
λ
2
≤
⋯
≤
λ
n. Then the number of spanning trees of the composition graphs of the complete 3-partite graph K
s
1
,
s
2
,
s
3 and the graph G is equal to
(27)
t
(
K
s
1
,
s
2
,
s
3
⊙
G
)
=
n
w
·
∏
i
=
1
3
‍
[
n
(
w
-
s
i
)
]
s
i
-
1
×
∏
i
=
1
3
‍
∏
k
=
2
n
‍
[
λ
k
+
n
(
w
-
s
i
)
]
(
n
-
1
)
s
i
,
where w
=
∑
j
=
1
3
‍
s
j is the order of K
s
1
,
s
2
,
s
3.Proof.
It follows directly from Lemma2 and Theorem 3.


## 3. Some Corollaries

As direct consequences, we give some corollaries of the above Theorem4.Corollary 1 (see [19]).
The number of spanning trees of the complete3-partite graph K
s
1
,
s
2
,
s
3 is equal to
(28)
t
(
K
s
1
,
s
2
,
s
3
)
=
w
∏
i
=
1
3
‍
(
w
-
s
i
)
s
i
-
1
,
where w
=
∑
j
=
1
3
‍
s
j is the order of K
s
1
,
s
2
,
s
3.Proof.
According to Theorem4, let G
=
K
1, and note that t
(
K
s
1
,
s
2
,
s
3
)
=
t
(
K
s
1
,
s
2
,
s
3
⊙
K
1
), n
=
1, and λ
(
K
1
)
=
0. The corollary follows immediately from Theorem 4.Corollary 2 (see [18]).
One has the following formulae:(29)
t
(
K
m
⊙
K
n
)
=
(
m
n
)
m
n
-
2
,
t
(
K
p
,
q
⊙
K
n
)
=
n
n
(
p
+
q
)
-
2
q
p
-
1
p
q
-
1
[
(
q
+
1
)
p
(
p
+
1
)
q
]
n
-
1
,
t
(
K
m
⊙
K
p
,
q
)
=
[
m
(
p
+
q
)
]
2
m
-
2
×
{
[
(
p
+
q
)
(
m
-
1
)
+
p
]
q
-
1
[
(
p
+
q
)
(
m
-
1
)
+
q
]
p
-
1
}
m
.Proof.
Note thatλ
i
(
K
n
)
=
(
0
,
(
n
-
1
)
n
-
1
),  i
=
1,2
,
…
,
n. Then the corollary follows immediately from Theorem 4.Finally, as direct consequences of Theorem4, we give closed formulae for the number of spanning trees of some new family of graphs.Corollary 3.
LetK
n be a complete graph, C
n a cycle with n vertices, and λ the nonzero eigenvalues of K
n; then the following results can easily be obtained:
(30)
t
(
K
n
⊙
K
s
,
s
,
s
)
=
(
n
)
3
n
-
4
·
(
3
s
)
3
n
-
2
·
(
3
n
s
-
s
)
3
(
n
-
1
)
(
s
-
1
)
,
t
(
C
n
⊙
K
s
1
,
s
2
,
s
3
)
=
n
3
2
n
w
3
n
-
2
∏
i
=
1
3
‍
(
3
w
-
s
i
)
n
(
s
i
-
1
)
.



---

*Source: 613685-2014-03-19.xml*