On Spanning Tree Edge Densities And Kirchhoff Indices Of Graphs

The spanning tree density and resistance distance are important research topics in graph theory and network theory.In this thesis,we consider two graph invariants based on spanning tree and resistance distance.One is the spanning tree edge dependence,and the other is the Kirchhoff index.Let G be a connected graph.A spanning tree of G is a connected subgraph without cycles which contains all the vertices of G.Suppose that the number of spanning trees of G is ?(G),and the number of spanning trees of G containing e is ?G(e).Then the ratio dG(e)=TG(e)/?(G)is called the spanning tree edge density of e(simply density of e).The maximum density among all the edges of G is called the spanning tree edge dependence of G,record as dep(G)=maxe?E(G)dG(e).In this thesis,we mainly study two conjectures on spanning tree edge dependencies,as well as resistive distances and Kirchhoff indices of hexagonalization of graphs.The whole thesis is divided into four chapters,as given in the following.Firstly,in the first chapter,we introduce concepts and notations which will be used in the thesis,and survey research progress on spanning trees,resistance distances,and Kirchhoff indices of graphs.Then,in chapter 2,we study two conjectures on spanning tree edge dependences.Given a rational number p/q ?(0,1),if there exists a graph G and an edge e ? E(G)such that dG(e)=p/q,then we say the spanning tree edge density p/q is constructible.More specially,if there exists a graph G such that dep(G)=p/q,then we say the spanning tree edge dependence p/q is constructible.In 2002,Ferrara,Gould,and Suffel raised the question that which rational spanning tree edge densities are constructible and which spanning tree edge dependences are constructible.In 2016,by construction of graphs,Kahl proved that all rational spanning tree edge densities and dependences are constructible.Moreover,Kahl observed that all rational spanning tree edge densities are constructible even if we restrict G to bipartite graphs or planar graphs.Based on this,Kahl conjectured that all rational spanning tree edge dependences are also constructible if G are restricted to bipartite graphs(Conjecture 1),or planar graphs(Conjecture 2).By combinatorial and electric network approach,firstly,we confirms the first conjecture of Kahl.Secondly,we proved that Conjecture 2 is true for planar multigraphs.However,for(simple)Next,in chapter 3,we consider the resistance distance and Kirchhoff index of the hexagonalization graph H(G)of a graph G.The haxagonalization graph H(G)is the graph obtained from G by replacing each edge of G by two disjoint paths of length 3 with the end vertices of the edge as their end vertices.Let Hk(G)denote the the graph obtained from G by k-iterated hexagonalizations.Using algebraic and combinatorial methods,explict formulae for resistance distances and Kirchhoff indices of H(G)and Hk(G)are obtained.It turns out that resistance distances and Kirchhoff indices of H(G)and Hk(G)could be expressed in terms of resistance distances and related structural graph invariants of G.Finally,in the last chapter,we make a brief summarization to this thesis,and propose problems that could be studied in the future.