Methods of Constructing and Enumerating the Spanning Tree of a Connected Graph

Abstract:

A definition concerning the spanning sub graph and spanning sub graph circle is given. Use the enumerating methods of spanning sub circle; seek out the spanning sub graph of spanning trees. The theorems of constructing and enumerating the spanning trees are proved. The methods of enumerating and constructing connected graph spanning tree are proposed. The application examples of construction theorem and enumerating theorem are given. the spanning sub graphs number of five plane graph and the construction of Constituent sub-graph are introduced, thus verifying constructing and enumerating theorem are useful and effective. This method Is a Simple and easy method to construct the spanning tree of connected graph.

• Periodical: Applied Mechanics and Materials (Volumes 496-500)
• Pages: 2363-2366
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.496-500.2363
• Online since: January 2014
• Authors: Zhao Di Xu, Xiao Yi Li, Wan Xi Chou
• Keywords: Construction, Enumeration, Spanning Sub Graph, Spanning Tree

References

[1] Zhang Y P，Yong X R，Golin m J. The numbers of spanning trees in circulant graphs[J]. Discrete Math，2000，223：337-350.

DOI: 10.1016/s0012-365x(99)00414-8

[2] YANG Y S. Computer algorithms of the whole spanning trees about undirected and directed graph[J]. Chinese Journal of Computers, 1983, （2）：152-154.

[3] LI C J. Formula about the number of spanning tree[J]. Practice and understanding of math, 1993，23（4）：63-65.

[4] CHOU W X. The Construction and Enumeration of Spanning Tree of Complete graph [J]. Journal of Shandong Normal University: Natural Science Edition, 2007，22（4）：72-73.

[5] CHEN D, WANG W F. The number of Some spanning tree graph[J]. Acta Mathematica Scientia，2008，28A（5）：906-913.

[6] LV D M, LV J J. Spanning trees number of tree expansion graph[J]. Journal of Liaoning University (Natural Science Edition), 2005，32(4)：306-308.