Resistance Distance Of Graphs And Its Applications

The resistance distance is a distance function on graphs and is a graph invariant. It is widely used in Computer Science, Physics, Chemistry, Biotechnology and so on. Let G(V, E) be a connected graph with vertex set V and edge set E. Every edge is replaced with an unit effective in the graph of G, then the electric network N is constructed. The resistance distance between any two vertices in G is defined to be the effective resistance between them in electric network of N. The Kirchhoff index of G is the sum of resistance distances between all pairs of vertices of G.In the graph theory, there are various matrices that are naturally associated with the resistance distance. The resistance distance matrix can be obtained according to transformation of the Laplacian matirx. In this thesis, some classes of graphs are defined and studied. They are the Q-graph Q(G), the extended wheel graph n3 W t C, the extended grid graph EX(m,n), the subdivision-vertex-vertex join 1 2G(9)G, the subdivision-edge-edge join 1G2 G, the subdivision-vertex-edge join 1G2 G. Then by using the Laplacian matrix, Genralized inverse or Group inverse, we calculate the resistance distance between any two points in the graph and the Kirchhoff index. Also, we propose a new method by compute program to quickly get the value of resistance distance and Kirchhoff index in extended wheel graphs and extended grid graphs. In this thesis, we get the main results as follows:(1) Obtain the formulas for resistance distance of the Q-graph of a graph G and use the formulas give resistance distance of Q-graph of complete graph, complete bipartite graph and circle graph.(2) Obtain the formulas for reistance distance of any pair of vertices of the subdivision-vertex-vertex join 1 2G(9)G, the subdivision-edge-edge join 1G2 G, the subdivision-vertex-edge join 1G2 G, and get the Kirchhoff index of these graphs.(3) Obtain the formulas for the resistance distance of any pair of vertices of the extended wheel graph and the Kirchhoff index of the extended wheel graph.(4) Calculate the of resistance distance of any pair of vertices of the extended wheel graph and the Kirchhoff index of the extended wheel graph by computer program. And get the value of resistance distance in extended grid graphs.(5) Propose an algorithm based on the resistance distance to detect the community structure.The algorithm is applied to the artificial network, the three community network and the Karate Club network, and the experiment results verify the validity of the algoithm.