Wiener And Kirchhoff Indices Of Graphs

Let G be a connected graph with vertex set V?G?.For i,j? V?G?,the distance between i and j is the length of a shortest path connecting them.The resistance distance between iandjis defined as the net effective resistance between them if each edge of G is replaced by a unite resistor.The Wiener index of G ,denoted by W?G?,is defined as the sum of distances between all pairs of vertices in G.The Kirchhoff index of G,denoted by Kf?G?,is defined as the sum of resistance distances between all pairs of vertices in G.The Wiener index and the Kirchhoff index are important graph invariants,which have widely used in QSAR and QSPR in chemistry.In this thesis,we focus on the Wiener index and the Kirchhoff index of graphs.The main content of this thesis is as follows.Firstly,unicyclic graphs with the fourth minimum and maximum Wiener indices are characterized.A connected graph with a unique cycle is called a unicyclic graph.The unicyclic graphs with the first three extremal Wiener indices have been characterized by researchers previously.Alone this line,we characterize unicyclic graphs with the fourth extremal Wiener indices.It is shown that among all unicyclic graphs with n? 8 vertices,C₅(S_n-4) and C₂^u1,u2(S₃,S_n-4) have the fourth minimum Wiener indices,whereas C₃^u1,u2(P₃,P_n-4) has the fourth maximum Wiener index.Secondly,complete solution is given to the conjecture regarding Nordhaus-Gaddum type result for the Kirchhoff index.In 2011,Yang,Zhang and Klein [Y.Yang,H.Zhang,D.J.Klein,New Nordhaus-Gaddum-type results for the Kirchhoff index,J.Math.Chem.49?2011?1587-1598] proposed a conjecture on the Nordhaus-Gaddum-type result for the Kirchhoff index.They conjectured that the sum of Kirchhoff indices of a graph G and its complement ??? attains its maximum if and only if G is the path graph P_n or ??? By making use of graph theoretical and electrical network theoretical methods and techniques,we give a complete solution to the conjecture.