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