TOPICS
Search

Resistance-Equivalent Graphs


Resistance-equivalent graphs are nonisomorphic simple graphs with equal resistance spectra, the multisets of resistance distances between unordered pairs of distinct vertices when each edge has unit resistance. For disconnected graphs, the resistance distance between vertices in different connected components is taken to be infinity.

ResistanceDistanceSame

All nonisomorphic simple graphs on eight or fewer vertices are determined by their resistance spectra. However, exactly 11 pairs of nonisomorphic graphs with nine vertices are resistance-equivalent, illustrated above (in the illustration, the numbers indicate the graph numbers in McKay's enumeration of 9-vertex graphs), where the second and third of these pairs were found by Baxter (1999b).

The numbers of simple graphs determined by their resistance spectra on n vertices for n=1, 2, ... are therefore given by 1, 2, 4, 11, 34, 156, 1044, 12346, 274646, 12005070, ... (OEIS A178944), and the numbers of graphs not determined by resistance are 0, 0, 0, 0, 0, 0, 0, 0, 22, 98, ... (OEIS A178999).

ResistanceEquivalent20

Rickard (1999a) found the pair of 20-vertex resistance-equivalent graphs illustrated above.

ResistanceEquivalent60

Baxter (1999b) subsequently conjectured that no nonisomorphic biconnected graphs were resistance-equivalent, a conjecture that was nearly immediately refuted by Rickard (1999b) with the pair of 60-vertex biconnected graphs obtained as the doubles of the graphs illustrated above.

All pairs of resistance-equivalent graphs listed above (for which the chromatic polynomial can be computed in reasonable time) are also chromatically equivalent graphs.


See also

Chromatically Equivalent Graphs, Resistance Distance

Explore with Wolfram|Alpha

References

Baxter, L. "Counterexamples Wanted--Graph Isomorphism & Resistances." Apr. 22, 1999a. https://groups.google.com/g/sci.math.research/c/G4g6Lkb-K9A/m/Y7jt-exp7lwJ.Baxter, L. "Counterexample Wanted for Graph Isomorphism Conjecture." Apr. 26, 1999b. https://groups.google.com/g/comp.theory/c/dP-LmP3DniE/m/Y4tSnBnzIeAJ.McKay, B. "Simple Graphs." https://users.cecs.anu.edu.au/~bdm/data/graphs.html.Rickard, J. "Counterexample Wanted for Graph Isomorphism Conjecture." Apr. 23, 1999a. https://groups.google.com/g/comp.theory/c/dP-LmP3DniE/m/dn047Thml1MJ.Rickard, J. "Counterexample Wanted for Graph Isomorphism Conjecture." Apr. 26, 1999b. https://groups.google.com/g/comp.theory/c/dP-LmP3DniE/m/uYfCq6Z_yx4J.Sloane, N. J. A. Sequences A178944 and A178999 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Resistance-Equivalent Graphs

Cite this as:

Weisstein, Eric W. "Resistance-Equivalent Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Resistance-EquivalentGraphs.html

Subject classifications