TOPICS
Search

Resistance-Equivalent Graphs


Two nonisomorphic graphs that have equal resistance spectra (i.e., multisets of resistance distances) are said to be resistance-equivalent.

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 determined by resistance graphs on n nodes 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 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." sci.math.research newsgroup posting. Apr. 22, 1999a.Baxter, L. "Counterexample Wanted for Graph Isomorphism Conjecture." comp.theory newsgroup posting. Apr. 26, 1999b.McKay, B. "Simple Graphs." http://cs.anu.edu.au/~bdm/data/graphs.html.Rickard, J. "Counterexample Wanted for Graph Isomorphism Conjecture." comp.theory newsgroup posting. Apr. 23, 1999a.Rickard, J. "Counterexample Wanted for Graph Isomorphism Conjecture." comp.theory newsgroup posting. Apr. 23, 1999b.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 Web Resource. https://mathworld.wolfram.com/Resistance-EquivalentGraphs.html

Subject classifications