Counterexamples wanted - Graph Isomorphism & Resistances
Lew Baxter
counterexamples from comp.theory.
-------------
Graph Isomorphism using Circuit Resistance
CONJECTURE
Two connected undirected graphs are isomorphic iff their resistance
spectrum's are equal.
Definition
For a graph G define the resistance spectrum of G, R(G) as follows. In G
replace every edge by a 1 ohm resistor. For vertices u, v (unequal) let
r(u,v) = resistance between vertices u and v. Then R(G) is the bag
containing all such r(u,v)'s.
For example, let G =
a----b----c
| |
| |
d----e
then r(a,b) = resistance between a and b in:
1 1
a----b----o
1| |1
| |
o----o
1
= resistance of 1 ohm and 3 ohm in parallel = (1*3)/(1+3) = 3/4.
Similarly,
r(a,c) = 7/4
r(a,d) = 3/4
r(a,e) = 1
r(b,c) = 1
r(b,d) = 1
r(b,e) = 3/4
r(c,d) = 2
r(c,e) = 7/4
r(d,e) = 3/4
and R(G) = [3/4, 3/4, 3/4, 3/4, 1, 1, 1, 7/4, 7/4, 2].
I have been experimenting with this on and (mainly) off for several years.
Finally, I recently I tested this successfully on all connected graphs with
up to 7 vertices, and plan to test for 8 and 9 vertices, and (stongly)
regular graphs.
I would appreciate any Please send me your proposed counterexamples for
testing, and other
comments.
Lew Baxter
---
S.D.Lew responded...
This is totally off the top of my head, but would this work
for a delta / wye network or a wheatstone bridge?
I think you can make a delta network out of resistors
(three segments for each side for a total of nine resistors)
and a wye-network out of one resistor segments, their
port resistances would be equal, but the networks are not
isomorphic.
This implies to me that it would be possible to construct a
complicated network that had a delta and a wye in the middle.
You could probably construct another network that had the
delta and wye swapped and have the same point to point
resistances, but not be isomorphic.
If this is true, you could probably also hide resistances inside
of a wheatstone bridge. A complicated network with two
wheatstone bridges in the middle, one with 1 resistor the other
with 2. Then in the non-isomorphic circuit, you swap them.
I guess it all depends on what you mean by a "bag" and
having the same "resistance spectrum".
>>> A BAG IS A SET WITH DUPLICATES
>>> TWO BAGS (OF RESISTANCES) ARE THE SAME IF THEY ARE IDENTICAL AFTER
SORTING.
There's probably some graph theory argument to support this,
but it's getting late and my brain isn't really working at full speed.
Cheers,
-slew
-----------
Replacing Wye with Delta does not affect the resistance between two vertices
not inside the Wye or Delta, but generally does for vertices inside.
Similarly for Wheatstones.
E.g. if WH1 =
o o o x
/|\ / \ /|\ / \
o o o o o o o
\|/ \ / \|/ \ /
y o o o
then R(G) = [14*2/3, 8*3/8, 10*1, 12*17/12, 6*5/3, 12*7/4, 6*2, 4*7/3,
4*5/2, 8*8/3, 4*11/4, 5*3, 4*41/12, 2*11/3, 4*15/4, 2*4]
If WH2 =
o u v o
/ \ /|\ / \ /|\
o o o o o o o
\ / \|/ \ / \|/
o o o o
then R(WH2) = [14*2/3,8*3/4,10*1, 4*4/3, 8*17/12, 12*5/3, 8*7/4, 8*2,
8*29/12, 4*8/3, 8*11/4, 4*3, 4*7/2, 4*15/4, 4].
("n*r" means n repetitions of r)
In particular r(x,y) = 41/12 which is not in R(WH2), and
r(u,v) = 4/3 is not in R(WH1).
Dave Wagner
Lew Baxter <lba...@interlog.com> wrote:
>Graph Isomorphism using Circuit Resistance
>
>CONJECTURE
>
>Two connected undirected graphs are isomorphic iff their resistance
>spectrum's are equal.
>
>Definition
>
>For a graph G define the resistance spectrum of G, R(G) as follows. In G
>replace every edge by a 1 ohm resistor. For vertices u, v (unequal) let
>r(u,v) = resistance between vertices u and v. Then R(G) is the bag
>containing all such r(u,v)'s.
This is an interesting conjecture, and seems plausible. One might as well
state it for networks (allowing multiple edges but not loops). Here is
a relevant observation: let G+uv be the network obtained from G by
adjoining a new edge between u and v. Let t(H) be the number of
spanning trees of the network H. Then
t(G+uv)
r(u,v) = ------- - 1. (*)
t(G)
>For example, let G =
>
> a----b----c
> | |
> | |
> d----e
>
>then r(a,b) =
>= resistance of 1 ohm and 3 ohm in parallel = (1*3)/(1+3) = 3/4.
or, one checks that t(G+ab)=7 and t(G)=4, so r(a,b) = 7/4-1 = 3/4.
So, an equivalent formulation of the conjecture is that every (connected)
network can be "reconstructed" from the multiset
{ t(G+uv): u,v distinct vertices of G }.
I believe the formula (*) goes back to Kirchhoff. It can be decoded from
(2.13) of [Brooks, Smith, Stone, and Tutte, The dissection of rectangles into
squares, Duke Math. J. 7 (1940), 312-340]. It appears with a new proof as
Proposition 5.3 in my paper [The algebra of flows in graphs, Adv. Appl.
Math. 21 (1998), 644-684].
Cheers,
David Wagner
--
David Wagner | dgwa...@math.uwaterloo.ca
Department of C & O | http://math.uwaterloo.ca/~dgwagner
University of Waterloo |
Waterloo, Ontario, Canada N2L 3G1 | "Hey, just enough room for a pithy quote!"
Timothy Chow
Dave Wagner <dgwa...@math.uwaterloo.ca> wrote:
>So, an equivalent formulation of the conjecture is that every (connected)
>network can be "reconstructed" from the multiset
>{ t(G+uv): u,v distinct vertices of G }.
So would the conjecture imply that graph isomorphism is in P?
Looking at known families of cospectral graphs (in the usual sense) would
seem to be a good start. _Spectra_of_Graphs_ by Cvetkovic, Doob, and Sachs
has lots of references for this. In view of the above connection with
spanning trees, one might also consult Russell Merris, "Laplacian matrices
of graphs: a survey," Lin. Algebra. Appl. 197 (1994), 143-176.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
Where a calculator like the ENIAC today is equipped with 18,000 vacuum tubes
and weighs 30 tons, computers in the future may have only 1,000 vacuum tubes
and perhaps weigh only 1 1/2 tons. ---Popular Mechanics, March 1949, p.258
John Rickard
counterexamples have been posted there in the thread "Counterexample
wanted for Graph Isomorphism Conjecture".
--
John Rickard <John.R...@virata.com>