Research On Resistance Distance And Kirchhoff Index Of Graphs

The resistance distance between any two vertices i and j in a connected graph G,denoted byΩG(i,j),is defined as the equivalent resistance between these two vertices in the electrical network N obtained by replacing each edge of the graph with a unit resistor.Based on the resistance distances,the resistance diameter Dr(G)is defined as the maximum resistance distance among all pairs of vertices in G.The Kirchhoff index K f(G)is defined as the sum of resistance distances between all pairs of vertices in G.The average resistance distance RD(G)is defined as the average value of the resistance distances between all pairs of vertices in G.In this thesis,we focus on the resistance distance and Kirchhoff index,resistance diameter,average resistance distance.The specific research content is described below.In chapter 1,we first introduce the basic concepts and notations,and introduce the research background,research progress and the main research methods which used in this thesis.In chapter 2,by the {1}-inverse of the Laplacian matrix of G,we obtain the formula for resistance distance between vertices in a given set of vertices in graph G.It turns out that resistance distances between vertices in this given set could be given in terms of elements in the inverse matrix of an auxiliary matrix of relevant Laplacian matrix,which derives the reduction principle obtained in[J.Phys.A:Math.Theor.41(2008)445203]by algebraic method.In chapter 3,we study the resistance diameter of the lexicographic product graph Pn[Pm].Recently,Li Yunxiang et al.studied the resistance diameter of graph Pn[Pm].Using properties of ordered graphs,they characterized the pairs of vertices that reach the resistance diameter in Pn[Pm]when n>10.For n=2,they provided a counterexample and proved that the result no holds.For 3 ≤n ≤10 and enough small m,with the aid of computer,they verified the conjecture is still true.First we establish some comparative results on the resistance distance of vertices in a weighted fan graph,and then determine vertex pairs that reach the maximum resistance distance in Pn[Pm]when n≥3,which affirms this conjecture in[J.Appl.Math.Comput.68(3)(2022)1743-1755].In chapter 4,we study the resistance diameter conjecture of graphs.In[Discrete Appl.Math.306(2022)174-185],Xu Si-ao et al.proposed the conjecture that the resistance diameter of a connected graph G is greater than or equal to the resistance diameter of its line graph LG,i.e.Dr(LG)≤Dr(G).We show that the conjecture is true for some class graphs and provide a formula for comparing the resistance diameters.As a consequence,we establish the validity of this conjecture for regular connected graphs.In chapter 5,we study the average resistance distance conjecture of graphs.Similar to the conjecture on average distance of graphs,we defined the average resistance distance and proposed a conjecture on it.We characterized several classes of graphs that satisfy this conjecture.In particular,the conjecture holds for regular connected graphs and 3-connected graphs.In chapter 6,we characterize the hexagonal chain with minimum Kirchhoff index.Using methods and techniques from graph theory and electrical network,we first obtain some properties of resistance distance in general hexagonal chains.Combining the comparison results on Kirchhoff index of S,T-isomers,"all-kink" chains with maximum and minimum Kirchhoff index are characterized.As a consequence,hexagonal chains with minimum Kirchhoff index are singled out.This completely solves an open problem proposed in[Discrete Appl.Math.175(2014)87-93].In chapter 7,we characterize the extremal pentagonal chain with respect to the Kirchhoff index.We first obtain some properties of the resistance distances in the pentagonal chain.Then,using these properties,we obtain comparison results on Kirchhoff index of pentagonal chains,which enables us to characterize extremal pentagonal chains with respect to Kirchhoff index.Finally in chapter 8,we summarize the main contents of this thesis,and propose some problems that could be studied in the future.