Filtering graphs to check isomorphism and extracting mapping by using the Conductance Electrical Model

Highlights：

• The method uses the CEM to model the graphs and detect the isomorphic graphs.

• The time complexity for detecting non-isomorphic graphs of N degree is in most of the cases O(N3).The CEM can obtain the complete or partial node mapping between the graphs.

• The time complexity for detecting graphs isomorphism in the worst time complexity can be exponential with respect to the number of repeated star values.The detection and mapping of a graph isomorphism (excluding co-resistances) are clearly separated, which allows doing the filter process in two phases.

• The filter performs an early detection of non-isomorphic graphs.

• The filtering process is not probabilistic, not iterative neither recursive, so the computation complexity is deterministic and only depends on N.

• We do not need to calculate the pseudoinverse, we can compute the star resistance values by a sum of finite number of terms.