The Number of Spanning Trees of General Fan Graphs

Published: 2023-10-30

Page: 79-94

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

Zhinan, Gao, Lu Xingyan, Wei Yuxuan, and Zhu Feng. 2023. “The Number of Spanning Trees of General Fan Graphs”. Asian Research Journal of Mathematics 19 (11):79-94. https://doi.org/10.9734/arjom/2023/v19i11755.

Downloads

Download data is not yet available.

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