Research On Enumerations Of Spanning Trees Of Some Digraphs

As an important branch of graph theory,the spanning tree counting of graphs plays a crucial role in relevant researches of graph theory,such as complex networks,random walks,structure analysis of graphs,etc.With the increasing application of spanning trees counting problem,it is found that directed graph is more significant than undirected graph in random walk and network control system.Many facts also tell us that the research on the graph of recursive construction or the operation graph spanning tree of directed graph can provide important theoretical basis for the design of network.Therefore,the research on spanning tree counting of directed graph is a basic and meaningful work.In this thesis,the definitions of some operational graphs of weighted directed graphs are introduced,and the definitions of many operational graphs under the background of undirected graphs is extended to directed graphs.By analyzing the vertex-weighted Laplacian matrix and Schur complement matrix of the composite graph generated by graph operation,the counting formulas of the rooted spanning tree of the vertex-weighted digraphs are given,such as directed division graph,directed R-graph,directed Join graph and directed Corona graph and so on.In particularly,when the weights of the vertices and arcs of the graph are all1,the counting formula of the rooted spanning tree of the composite graph generated by graph operation is obtained.