Suppose, transformation T
is defined as given in the diagrams below.
Every vertex (v
) is replaced by deg(v)-gon
. And then graph is reconnected as shown.
Those on the left are G
s and on the right are T(G)
s.
It is easy to see that every vertex in T(G)
has degree 3
.
This paper claims that graph isomorphism of such graphs can be tested in polynomial time. Also, G
can be converted to T(G)
in polynomial time.
Statement I: G1 and G2 are isomorphic iff T(G1) and T(G2) are isomorphic.
EDIT:
Specifications for G1,G2:
- G1 = (V1,E1) and G2=(V2,E2)
- |E1| = |E2| and |V1| = |V2|
- Sort[{deg(v)|v in V1}] = Sort[{deg(u)| u in V2}]
If Statement I is True
then do we have solution for GI problem?
Note: I am n00b in this field. I invent funny techniques daily.