Research On Several Problems Of Spanning Tree Countin

For a graph G,a connected and acyclic subgraph of G is called a tree.The number of spanning trees of a graph is a well-studied isomorphic invariant in graph theory and other related fields.Let G be a subgraph of the complete graph Kn.The Kn-complement of G,denoted by Kn-G,is the graph resulting by removing the edges of G from Kn.In this thesis we examine the problem of calculating the number of spanning trees of Kn-G for a bipartite graph G in a very straightforward manner and derive formulas for their number of spanning trees of Kn-complements of various important classes of bipartite graphs including disjoint edges,disjoint paths,disjoint cycles,disjoint stars and disjoint complete bipartite graphs,which generalize previous results and extend the family of graphs of the form Kn-G admitting formulas for the number of their spanning trees.Our proofs are heavily relying on Kirchhoff’s celebrated Matrix-Tree-Theorem and an expansion of the determinant of the sum of two square matrices,one of which is a diagonal matrix.Specially,assuming that G is a bipartite graph and the rank of its adjacency matrix is less than 6,by using the method raised in this thesis,an exact expression for the number of spanning trees of the Kn-complement of G is obtained by terms of the number of some substructures up to isomorphism such as an edge K2,two disjoint edges 2K2,the path P3,the cycle C6 and so on.Moreover,let Knm be the complete multigraph with n vertices and m edges between any two distinct vertices,and let Knm+G(Knm-G)be the resulting graph obtained from Knmby adding(removing)all edges of a subgraph G of Knm.Based on MatrixTree-Theorem and complicated determinant caculations,Nikolopoulos and Papadopoulos obtained the number of spanning trees of Knm±G as follows:τ(Knm±G)=m(mn)n-p-2 det(mnIp±L(G)),where |V(G)|=p and L(G)is the Laplacian matrix of G.In this thesis,by using some linear algebra techniques(a special formula on a determintant of the sum of two matrices),a new simple proof for above-mentioned formula was given,Further,some results on τ(Knm±G)were shown when G is a complete graph,a cycle,a path and a complete bipartite graph,respectively.