Aporntewan, C., Chaiyaratana, N., Chongstitvatana, P., "Indexing Simple Graphs by Means of the Resistance Distance," IEEE Access, August 2016.

Abstract

For every simple connected graph, we present a polynomial time algorithm for computing a numerical index which is composed of primary and secondary parts. Given a graph G = (V, E)  where V and E are respectively vertex and edge sets, the primary part of the index is a set of  | V | fractions and the secondary part of the index is a set of | V | × | B | fractions where B is the partition of the vertex set V. Basically each fraction in the primary and secondary parts is the electrical resistance between two vertices when every edge in the graph is replaced with a unit resistor (1 Ω). The experimental results show that our indexing algorithm produced a unique index for every simple connected graph with ≤ 10 vertices, including all graphs that are counterexamples for detecting graph isomorphism by resistance spectrum comparison. The strength of our indexing algorithm lies in its extreme simplicity. An index of a graph is solely derived from determinants of reduced Laplacian matrices which represent the graph. Therefore, the performance of our indexing algorithm only depends on how fast the matrix determinants can be computed.