The Number of Spanning Trees of General Fan Graphs
Gao Zhinan
School of Mathematical Sciences, Jiangsu University, China.
Lu Xingyan
School of Mathematical Sciences, Jiangsu University, China.
Wei Yuxuan
School of Mathematical Sciences, Jiangsu University, China.
Zhu Feng *
School of Mathematical Sciences, Jiangsu University, China.
*Author to whom correspondence should be addressed.
Abstract
As we all know, the number of spanning trees can be calculated by virtue of the famous Kirchhoff’s matrix-tree theorem. However, it doesn’t work when coming across complex graphs with thousands of edges and vertices or more. Hence, how to obtain accurate solutions of the number of spanning trees of general fan graphs becomes a subject to several studies of many places like computer science, physics and mathematics. In this paper, we focus on calculating different types of graphs generated by adding vertices and edges to the fan graph. Particularly, we define a new graph called "C-graph", which brings a unique angle of view for us to recognize the construction of original graphs. Moreover, we introduce a new iterative relation about the general fan graph, simplifying the calculation. Therefore, we can obtain functions of the number of spanning trees obtained from given fan graphs, which are also suitable for larger and more complex conditions. Finally, we discuss the effect of vertices and edges on the number of spanning trees, finding out that edges have greater impact. Additionally, by using Kirchhoff’s matrix-tree theorem, we verified the rationality of our results.
Keywords: Fan graphs, spanning trees, iterative relations, self-similar graphs, Kirchhoff’s matrix-tree theorem
How to Cite
Downloads
References
Kalyagin VA, Koldanov AP, Koldanov Petr. Reliability of maximum spanning tree identification
in correlation-based market networks. Physica A: Statistical Mechanics and its Applications.
;599(04):127482. DOI: 10.1016/j.physa.2022.127482
Hanjie Liu, Jinren Zhang, Qingshan Liu, Jinde Cao. Minimum spanning tree based graph neural network
for emotion classification using EEG. Neural Networks. 2022;145:308-318.
Daoud SN. The deletion-contraction method for counting the number of spanning trees of graphs. The
European Physical Journal Plus. 2015;130(10). DOI: 10.1140/epjp/i2015-15217-y
Daoud SN. Complexity of graphs generated by wheel graph and their asymptotic limits. Journal of the
Egyptian Mathematical Society. 2017;25(08). DOI: 10.1016/j.joems.2017.07.005
Liu, Jia-Bao, Daoud SN. Number of spanning trees in the sequence of some graphs. Complexity.
;2019(03):1-22. DOI: 10.1155/2019/4271783
Shrock Robert, Wu FY. Spanning trees on graphs and lattices in d dimensions. Journal of Physics A:
Mathematical and General. 2000; 33(21):3881.
Teufl, Elmar, Wagner, Stephan. The number of spanning trees in self-similar graphs. Annals of
Combinatorics. 2011;15(06):355-380. DOI: 10.1007/s00026-011-0100-y
Kirchhoff, G. Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen
Vertheilung galvanischer Ströme geführt wird. Annals of Combinatorics.1847;497-508.
Bibak, Khodakhast, Haghighi, Mohammad. Recursive relations for the number of spanning trees. Applied
Mathematical Sciences (Ruse). 2009;3(01).
Aichholzer O, Hackl T, Korman M, Van Kreveld M, Löffler M, Pilz A, Speckmann B,Welzl E. Packing plane
spanning trees and paths in complete geometric graphs. Information Processing Letters. 2017;124(08):35-41.
Feng et al.; Asian Res. J. Math., vol. 19, no. 11, pp. 79-94, 2023; Article no.ARJOM.107955
Ma, Fei, Yao, Bing. An iteration method for computing the total number of spanning trees and its
applications in graph theory. Theoretical Computer Science. 2017;708(11). DOI: 10.1016/j.tcs.2017.10.030
Sahbani, Hajar, El marraki, Mohamed. On the number of spanning trees in graphs with multiple edges.
Journal of Applied Mathematics and Computing. 2016;55(07). DOI: 10.1007/s12190-016-1034-7