Resistance Distances And The Number Of Spanning Trees Of Several Families Of Graphs

Resistance distance is an important invariant defined on graphs,and it is a classic problem of circuit theory and graph theory.It is derived from the equivalent resistance in electrical networks,and has several applications in combinatorics and probability theory.Counting spanning trees of graphs has a long history and is still an active topic now.The number of spanning trees is a key index in exploring network reliability with much applications.Resistance distance and the number of spanning trees of a graph are also closely related.In this thesis we will study resistance distance and the number of spanning trees in several families of graphs.Complete graphs and complete bipartite graphs are special in structure and have extremely strong symmetry.It is relatively easy to compute the resistance distance and the number of spanning trees in complete graphs and complete bipartite graphs.We make some reasonable changes to the structure of these graphs by deleting some substructures(such as cycles,paths).It will weaken some local symmetries of complete graphs and complete bipartite graphs,which will greatly increase the difficulty of computing resistance distance and the number of spanning trees.In this thesis,we discuss which methods are more effective in computing the resistance distance and the number of spanning trees in these graphs.For some special graphs,resistance distance and the number of spanning trees can be completely determined.This thesis is organized as follows:In Chapter 1,we introduce the research background,current situation and we briefly explain the content of this thesis.In Chapter 2,we give some common symbols and basic knowledge in this topic.In Chapter 3,we study the resistance distance in graphs,especially in complete graph and the complete bipartite graph deleting a path or a cycle.In Chapter 4,we consider the number of spanning trees of complete graph and complete bipartite graph deleting a path or a cycle.In Chapter 5,we summarize the main results and propose some problems for further research.