![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
ABSTRACT
Boesh and Prodinger have shown how to use properties of Chebyshev polynomials to compute formulas for the number of spanning trees of some special graphs. In this paper, we extend this idea for some operations on graphs such as, Join and Corona of two graphs and
, if
and
are one of the following graphs: (i) Path graph
, (ii) Cycle graph
, (iii) Complete graph
, (iv) Complete bipartite
, (v) Hypercube graph
, (vi) Fan graph
and (vi) Wheel graph
.
1. Introduction
The study of the number of spanning trees in a graph has a long history and has been very active because computing this number is important: (1) in analysing energy of masers in investigating the possible particle transitions; (2) in estimating the reliability of a network; (3) in designing electrical circuits; (4) in enumerating certain chemical isomers; (5) in counting the number of Eulerian circuits in a graph [Citation1–10].
The number of spanning trees of a finite undirected graph
is equal to the total number of distinct spanning subgraphs of
that are trees. This quantity is also known as the complexity of
. There exist various methods of finding this number. Let us recall the famous Matrix tree theorem of Kichhoff [Citation11]: The complexity
of a graph
is equal any cofactor of Laplace matrix
, where
is the diagonal matrix of vertex degrees of
and
is the adjacency matrix of
.
Another way to compute the number of spanning trees a graph, is to recursively degenerate the graph by deleting and contracting edges. In this way, the number of spanning trees of an unknown graph is reduced to a sum of the number of spanning trees in small graphs which is well known. Let
be an edge with endpoints
and
in the graph
, the contraction
of
from
is the graph obtained by removing
and identifying
and
. The deletion
of
from
is the graph obtained by removing
. The formula for counting spanning trees in a graph
is
(see [Citation12,Citation13]).
Another way to compute the number of spanning trees in a graph is using linear algebra. Let be a graph with vertex set is
with non-increasing degree sequence
, where
is the degree of vertex
for
The eigenvalues of
are called the Laplacian eigenvalues (Spectrum) and denoted by
It is well known that
The following formula in terms of Laplacian eigenvalues of is well known by Kelmans and Chelnoknov [Citation14] as:
(1)
(1)
By
, we denote the Laplacian spectrum of
. For a graph
of order
, we write
with the understanding that
2. Some properties of Chebyshev polynomial
In this section, we introduce some relations concerning Chebyshev polynomials of the first and second kind which we use in our computations [Citation15].
The Chebyshev polynomials of the first kind are defined by:
(2)
(2)
It is easily verified that
(3)
(3)
Furthermore by using standard methods for solving the recursion (3), one obtains the explicit formula:
(4)
(4)
The Chebyshev polynomials of the second kind are defined by:
(5)
(5)
It is easily verified that
(6)
(6)
Furthermore by using standard methods for solving the recursion (6), one obtains the explicit formula:
(7)
(7)
We have, Hence
(8)
(8)
One further notes that:
(9)
(9)
These two results yield another formula for ,
(10)
(10)
Simple manipulation of the above formula yields the following, which also will be extremely useful to us latter:
(11)
(11)
One further notes that:
(12)
(12)
(13)
(13)
Polynomials
and
are related by the following identity
(14)
(14)
Fibonacci numbers,
.are defined by recursive relation
(15)
(15)
With initial conditions
and
[Citation16].
An interesting fact follows by comparing (7) with the well known closed form formula for the Fibonacci numbers .
(16)
(16)
namely,
(17)
(17)
The Lucas numbers, are defined by recursive relation
(18)
(18)
with initial conditions
and
[Citation17].
Also we can prove that:
(19)
(19)
3. Complexity of the join of two graphs
The join of two graphs and
is the graph
. This is the union of two graphs
and
, with every vertex in
connected to every vertex in
. We note that
is always connected [Citation18].
Theorem 3.1:
Let and
be graphs on disjoint sets of
and
vertices respectively. If
and
are the eigenvalues of
and
arranged in non-increasing order, then the eigenvalues of
are
and
.
Proof
The adjacency matrix of can be defined as:
Let be all one column vector of length
, the degree sequence of
,
Thus the degree matrix of can be defined as
and hence the Laplacian matrix of
is
.
From this we may readily deduce the Laplacian spectrum of by exhibiting a complete set of eigenvectors. If
is an eigenvector of
corresponding to
,
, then the vector
,
and
otherwise, can be seen to be an eigenvector of
with eigenvalue
.
Similarly, we obtain the eigenvalue for
. The all ones vector gives as usual, the eigenvalue
, and the eigenvector whose value is
on the vertices of
and
on the vertices of
gives the eigenvalue
.
Lemma 3.1:
Let be the Laplacian matrix of the fan graph
. Then its eigenvalues are
Proof
The Laplacian matrix of the fan graph can be defined as:
Straightforward induction using properties of determinants, we have
Applying Lemma 3.1 by the author in [Citation19], we get:
Using identity (8), we have:
Therefore, implies,
Lemma 3.2
Let be the Laplacian matrix of the wheel graph
. Then its eigenvalues are
Proof
The Laplacian matrix of the wheel graph can be defined as:
Straightforward induction using properties of determinants, we get
Applying Lemma 3.2 by the author in [Citation20] together with Equation (14), we get:
Thus, implies,
Now we can introduce the following theorem:
Theorem 3.2
Let and
be graphs on disjoint sets of
and
vertices respectively. If
and
are the eigenvalues of
and
, then
Theorem 3.5
For and
, we have
Proof
The eigenvalues of
and
are
and
, respectively. Then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equation (7).
The eigenvalues of
and
are
and
, respectively. Then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equations (4) and (7).
The eigenvalues of
and
are
and
, respectively. Then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equation (4).
The eigenvalues of
and
are
and
, respectively. Then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equation (7).
The eigenvalues of
and
are
and
, respectively. Then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equation (4).
The eigenvalues of
and
are
and
, respectively. Then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equation (7).
The eigenvalues of
and
are
and
, respectively. Then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equation (4).
The eigenvalues of
and
are
and
, respectively. Then applying Equation (1) together with Theorem 3.2, we get
The eigenvalues of
and
are
and
, respectively. Then applying Equation (1) together with Theorem 3.2, we get
The eigenvalues of
and
are
and
, respectively. Then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equation (7).
The eigenvalues of
and
are
and
, respectively. Then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equation (4).
Theorem 3.4
For and
, we have
Proof
The eigenvalues of
and
are
and
, respectively, then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equation (7).
The eigenvalues of
and
are
and
, respectively, then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equation (4).
The proofs of (iii–v) follows similarly, using the facts, the eigenvalues of and
are
; and
, respectively.
Theorem 3.5
For and
, we have
Proof
The eigenvalues of
and
are
and
, then applying Equation (1) together with Theorem 3.2, we get
The proofs of (ii–vi) follows similarly, using the facts, the eigenvalues of and
are
;
;
and
, respectively, as follows:
The explicit formula follows from Equations (4) and (7).
Theorem 3.6
For and
, we have:
Proof
The eigenvalues of
and
are
and
, then applying Equation (1) together with Theorem 3.2, we get
The explicit formula follows from Equations (4) and (7).
The proofs of (ii–vii) follows similarly, using the facts, the eigenvalues of and
are
;
;
and
, respectively, as follows:
The explicit formula follows from Equations(4) and (7).
4. Complexity of corona of two graphs
The corona of two graphs
and
is the graph obtained by taking one copy of
(which has
vertices) and
copies of
and then joining the i-th vertex of
to every vertex in the copy of
[Citation21]. It is easy to see that
is not isomorphic
.
Theorem 4.1
[Citation22] Let and
be graphs of order
and
respectively. If Let
and
be graphs of order
and
respectively. If
and
are the eigenvalues of
and
arranged in non-increasing order, then the eigenvalues of
is given by the eigenvalues
with multiplicity
for
and
for
Now we can introduce the following theorem:
Theorem 4.2
Let and
be graphs of order
and
respectively. If
and
are the eigenvalues of
and
, then
Theorem 4.3
For , we have
Proof
Applying Theorem 4.2, we get
The explicit formula follows from Equations (17) and (19).
Theorem 4.4
For , we have
Proof
Applying Theorem 4.2, we get:
Theorem 4.5
For and
, we have
Proof
Applying Theorem 4.2, we get:
Theorem 4.6
For and
, we have
Proof
Applying Theorem 4.2, we get:
The explicit formula follows from Equations (4), (7), (17) and (19).
5. Conclusions
In this work, we investigate the spectrum of the Laplacian matrix of some operations on graphs such as, Join and Corona product. Using spectral graph theory, we proved some interesting trigonometric identities, these identities are of special interest to engineers, physicists and mathematicians. We can also develop, using this technique another set of identities.
Acknowledgments
The author would like to record their indebtedness and thankfulness to the reviewers for their valuable and fruitful comments as well as for their powerful reading and suggestions.
Disclosure statement
No potential conflict of interest was reported by the author.
ORCID
S. N. Daoud http://orcid.org/0000-0003-3809-2521
References
- Applegate DL, Bixby RE, Chvátal V, et al. The traveling salesman problem: a computational study. Princeton (NJ): Princeton University Press; 2006.
- Cvetkovie˘ D, Doob M, Sachs H. Spectra of graphs: theory and applications. 3rd ed. Heidelberg: Johann Ambrosius Barth; 1995.
- Kirby EC, Klein DJ, Mallion RB, et al. A theorem for counting spanning trees in general chemical graphs and its particular application to toroidal fullerenes. Croat Chem Acta. 2004;77:263–278.
- Boesch FT, Salyanarayana A, Suffel CL. A survey of some network reliability analysis and synthesis results. Networks. 2009;54:99–107. doi: 10.1002/net.20300
- Boesch FT. On unreliability polynomials and graph connectivity in reliable network synthesis. J Graph Theory. 1986;10:339–352. doi: 10.1002/jgt.3190100311
- Wu FY. Number of spanning trees on a lattice. J Phys A. 1977;10:113–115. doi: 10.1088/0305-4470/10/6/004
- Zhang F, Yong X. Asymptotic enumeration theorems for the number of spanning trees and Eulerian trail in circulant digraphs & graphs. Sci China Ser. 1999;A43(2):264–271.
- Chen G, Wu B, Zhang Z. Properties and applications of Laplacian spectra for Koch networks. J Phys A Math Theor. 2012;45:025102. doi: 10.1088/1751-8113/45/2/025102
- Atajan T, Inaba H. Network reliability analysis by counting the number of spanning trees. ISCIT 2004, IEEE International Symposium on Communication and Information Technology 1; Sapporo, Japan; 2004. p. 601–604.
- Brown TJN, Mallion RB, Pollak P, et al. Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes. Discrete Appl. Math. 1996;67:51–66. doi: 10.1016/0166-218X(96)85158-4
- Kirchhoff GG. Über die auflösung der gleichungen auf welche man bei der untersucher der linearen verteilung galuanischer strome gefhrt wird. Ann Phg Chem. 1847;72:497–508. doi: 10.1002/andp.18471481202
- Biggs NL. Algebraic graph theory. 2nd ed. Cambridge: Cambridge University Press; 1993. p. 205.
- Daoud SN. The deletion-contraction method for counting the number of spanning trees of graphs. Eur J Phys Plus. 2015;130(10):1–14. doi: 10.1140/epjp/i2015-15217-y
- Kelmans AK, Chelnokov VM. A certain polynomial of a graph and graphs with an extremal number of trees. J Comb Theor B. 1974;16:197–214. doi: 10.1016/0095-8956(74)90065-3
- Boesch FT, Prodinger H. Spanning tree formulas and Chebyshev polynomials. J Graphs Comb. 1986;2:191–200. doi: 10.1007/BF01788093
- Andrews G. Number theory. London: W. B. Saunders Company; 1971.
- Guiduli B. Topics in theory of number. Hungary: Springer Sciences; 2003.
- Balakrishnan R, Ranganathan K. A textbook of graph theory. New York (NY): Springer; 2000.
- Daoud SN. Complexity of cocktail party graph and crown graph. Am J Appl Sci. 2012;9(2):202–207. doi: 10.3844/ajassp.2012.202.207
- Daoud SN. Generating formulas of the number of spanning trees of some special graphs. Eur J Phys Plus. 2014;129(7):1–14. doi: 10.1140/epjp/i2014-14146-7
- Harary F. Graph theory. Reading (PA): Addison-Wesley; 1969.
- Liu Q. The Laplacian spectrum of corona of two graphs. Kragujevac J Math. 2014;8:163–170. doi: 10.5937/KgJMath1401163L