Research On Resistance Distance Rules And The Kirchhoff Index Of Graphs

The resistance distance r_ij between vertices i and j of a connected graph G is computed as the effective resistance between nodes i and j in the corresponding network constructed from G by replacing each edge of G with a unit resistor.The Kirchhoff index Kf(G) is the sum of resistance distances between all pairs of vertices of G.In this thesis,we mainly study resistance distances and the Kirchhoff index of graphs.We establish some rules on resistance distances,obtain Kirchhoff index formulae for linear hexagonal chains and three types of composite graphs,determine bounds for unicyclic graphs and Fullerene graphs,and give a new Nordhaus-Gaddum-type result for the Kirchhoff index.This thesis consists of seven chapters.In chapter 1,we first introduce some basic concepts,terminology and notations.Then we point out the physical-chemical research backgrounds.Finally,we survey the research developments in this area and make a brief introduction to the main results obtained in the thesis.Motivated by the work of Klein[Croat.Chem.Acta 75(2002) 633-649],in the second chapter,some rules for resistance distances of a graph G are established.Let S be a set of vertices of G such that all vertices in S have the same neighborhood N in G-S. If |S|=2,3,4,simple formulae are derived to compute resistance distances between vertices in S in terms of the cardinality of N.These show that resistance distances between vertices in S depend only on the cardinality of N and the induced subgraph G[S].One question arises naturally:does this property hold for S with arbitrarily many vertices? We answer this question positively by the following reduction principle: resistance distances between vertices in S can be computed as in the subgraph obtained from G[S∪N]by deleting all the edges between vertices in N.In chapter 3,first of all,according to the decomposition theorem of Laplacian polynomial, we obtain that the Laplacian spectrum of linear hexagonal chain L_n consists of the Laplacian spectrum of path P_2n+1 and eigenvalues of a symmetric tridiagonal matrix of order 2n+1.By applying the relationship between roots and coefficients of the characteristic polynomial of the above matrix,explicit closed-form formula for the Kirchhoff index of L_n is derived in terms of Laplacian spectrum.To our surprise,the Krichhoff index of L_n is approximately to one half of its Wiener index.Finally,we show that(Kf(G))/(W(G))>1/5 holds for all graphs G in a class of graphs including L_n,where W(G) denotes the Wiener index of G.Let S_n^l denote the graph obtained from cycle C_l by adding n-l pendant edges to a vertex of C_l and P_n^l the graph obtained from cycle C_l by identifying one endvertex of path P_n-l+1 with any vertex of C_l.In the forth chapter,we show that among n-vertex unicyclic graphs,(â…°) if n<8,C_n has minimal Kirchhoff index;if 8≤n＜12,S_n⁴ has minimal Kirchhoff index;if n = 12,both S_n³ and S_n⁴ have minimal Kirchhoff index; otherwise,S_n³ has minimal Kirchhoff index;(â…±)P_n³ has maximal Kirchhoff index.Sharp bounds for the Kirchhoff index of unicyclic graphs are then obtained.A Fullerene graph is a three-regular and three-connected plane graph exactly 12 faces of which are pentagons and the remaining faces are hexagons.In chapter 5, bounds for the Kirchhoff index of plane graphs especially Fullerene graphs are obtained.Let G₁+G₂,G₁ o G₂ and G₁{G₂} be the join,corona and cluster of graphs G₁ and G₂,respectively.In the sixth chapter,Kirchhoff index formulae of these composite graphs are given.A Nordhaus-Gaddum-type result is a(tight) lower or upper bound on the sum or product of a parameter of a graph and its complement.In a recent work[Chem.Phys. Lett.455(2008) 120-123],Zhou and Trinajsti(?) obtained a Nordhaus-Gaddum-type result for the Kirchhoff index.In the last chapter,we obtain a new Nordhaus-Gaddumtype result for the Kirchhoff index which improves the result obtained by Zhou and Trinajsti(?).