Counterexample wanted for Graph Isomorphism Conjecture
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).
John Rickard
: CONJECTURE
:
: Two connected undirected graphs are isomorphic iff their resistance
: spectrum's are equal.
[Resistance spectrum = multiset of resistances between pairs of
vertices.]
Counterexample:
* * *
| | |
* * * * *
| | | | |
*---*---*---*---*---* and *---*---*---*---*---*
| | | |
*---*---*---*---*---* *---*---*---*---*---*
| | | | | | |
* * * * * * *
|
*
--
John Rickard <John.R...@virata.com>
John Rickard
: Consequently, I will now strenghten the conjecture to BICONNECTED graphs.
:
: Two biconnected undirected graphs are isomorphic iff their resistance
: spectrums are the same.
"Biconnected" = "vertex 2-connected": that is, connected and removal
of any vertex leaves it connected?
In that case, I think I have a counterexample. 60 vertices, but there
probably exists a smaller one.
Consider the rooted trees A and B:
* *
\ \
* * * * * *
\ / / \ \ /
* * * *
\ / \ /
* *
A B
These have the same number of vertices of each degree at each distance
from the root. It follows that the two trees T and U:
+---+ +---+ +---+ +---+
| A | | B | | A | | A |
+---* *---+ +---* *---+
\ / \ /
*---* *---*
/ \ / \
+---* T *---+ +---* U *---+
| A | | B | | B | | B |
+---+ +---+ +---+ +---+
have, for each d, d', k, the same number of pairs of vertices V of
degree d and V' of degree d' at distance k.
Now "double" these two trees, giving graphs D(T), D(U), by replacing
each vertex V with two vertices V1, V2, and each edge VW with four
edges V1 W1, V1 W2, V2 W1, V2 W1. In calculating the resistance
between two vertices Vi and Wj (i, j in {1,2}) of such a doubled
graph, one can, by symmetry, fuse X1 and X2 for each vertex X other
than V and W; then, if the original graph is a tree, vertices other
than V, W, their neighbours, and those on the path between V and W
make no difference to the resistance, so the resistance depends only
on the degrees of V and W and their distance. (Or, in the case V = W,
i =/= j, it depends only on the degree of V.)
It follows that the resistance spectrums of D(T) and D(U) are the
same. But it's easy to see that D(T) and D(U) are biconnected and not
isomorphic.
--
John Rickard <John.R...@virata.com>
Lew Baxter
In the meantime I found that there are no counterexamples up to 8 vertices,
but several for 9 vertices, e.g. the pairs:
o o o--o o
| | \ /
o--o--o--o--o o--o--o
| | / \
o o o--o o
and
o o o o o
\ / \ / \ /
o--o--o o--o---o--o
/ \ | |
o---o o o
| |
o o
Consequently, I will now strenghten the conjecture to BICONNECTED graphs.
Two biconnected undirected graphs are isomorphic iff their resistance
spectrums are the same.
I haven't finished analyzing all 261080 connected graphs on 9 vertices, so I
don't know if there
any biconnected counterexamples there.
Note that isomorphism of graphs is polynomially reducible to the biconnected
case.
Dave Wagner
> Lew Baxter <lba...@interlog.com> wrote:
> : Consequently, I will now strenghten the conjecture to BICONNECTED graphs.
> : Two biconnected undirected graphs are isomorphic iff their resistance
> : spectrums are the same.
> "Biconnected" = "vertex 2-connected": that is, connected and removal
> of any vertex leaves it connected?
> In that case, I think I have a counterexample. 60 vertices, but there
> probably exists a smaller one.
[counterexample snipped.]
How about this (weaker) form of the conjecture...
For a (loopless, connected multi)graph G = (V,E) define a function
R(G): VxV --> rationals by R(v,v) = 0 for all v in V and R(v,w) is
the resistance between v and w in G when v != w. We might as well
represent R(G) by an n-by-n symmetric matrix if G has n vertices.
Certainly, if G and H are isomorphic then there is a permutation matrix P
such that P.R(G) = R(H).P. Let A(G) be the adjacency matrix of G.
CONJECTURE: If G and H are such that there is a permutation matrix P
such that P.R(G) = R(H).P then P.A(G) = A(H).P. (So P determines an
isomorphism from G to H.)
This is weaker than Baxter's conjecture since the hypothesis is stronger.
Do the counterexamples given for Baxter's conjecture remain counterexamples for
this? (Note: given R(G) and R(H), one must still find a P which satisfies
the hypothesis, so it doesn't look like this implies that GRAPH ISOMORPHISM
is polynomial-time solvable.)
Variation... define T(G): VxV --> integers by T(v,v) = 0 and
T(v,w) = t(G+vw), the number of spanning trees of G with a new edge v--w.
CONJECTURE': If G and H are such that there is a permutation matrix P
such that P.T(G) = T(H).P then P.A(G) = A(H).P. (So P determines an
isomorphism from G to H.)
(I reneg on my earlier posting... i don't see whether the variants
using r(u,v) versus t(G+uv) are or are not equivalent. (?))
Cheers,
Dave Wagner