The Study Of Several Problems On Kirchhoff Index Of Graphs

In a graph,if each edge is replaced by a resistor of unit resistance,then the resistance distance between two vertices is the effective resistance between these two vertices.Kirchhoff index is the sum of resistance distances between all pairs of vertices.It also can be indicated by the Laplacian spectrum of the graph.It has wide applications in chemistry and physicsThe edge k-partiteness of G is the minimum number of edges whose deletion from G yields a k-partite graph.In this paper,we study some problems to determine the minimum Kirchhoff index of graphs with a given edge k-partiteness.First,we theoretically characterize the graphs with minimum Kirchhoff index in this graph family when the edge k-partiteness is not big compared to the number of vertices of G.Then we propose an exhaustive search algorithm to find the optimal graphs.At last,three strategies were used to reduce the computation complexity of our algorithm and found the approximate optimal graphs.Several performance comparisons of these strategies are given.