5
$\begingroup$

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.

enter image description here

Those on the left are Gs 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:

  1. G1 = (V1,E1) and G2=(V2,E2)
  2. |E1| = |E2| and |V1| = |V2|
  3. 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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I don't understand why every vertex in $T(G)$ has degree $3$. If you have a vertex in $G$ with degree $1$ it has also degree $1$ in $T(G)$ or not? $\endgroup$ – Marc Bury Feb 18 '11 at 17:14
  • $\begingroup$ No. Suppose there is a vertex with degree 1. Then it will become a vertex with self-loop. Self-loop will add 2 degrees. $\endgroup$ – Pratik Deoghare Feb 18 '11 at 17:50
  • $\begingroup$ Considering a solver for GI as goal, you should copy the exact graph definition from GI here. I was under the impression that all standard graph problems were formulated with simple graphs, but I might be wrong there. $\endgroup$ – Raphael Feb 18 '11 at 19:51
  • 2
    $\begingroup$ Putting to the side the issues about isomorphism, the graph operation suggested by the top diagram, when applied to planar 3-connected graphs (which are the 3-polytopal graphs), corresponds to the idea of truncation of a vertex of the polytope associated with the graph. In particular, the new graph will be planar and 3-connected and sometimes reflects nice properties of the original polytope. For example, if one has a hamiltonian polytope and truncates a 3-valent vertex one gets a new 3-polytope which still has a hamiltonian circuit. $\endgroup$ – Joseph Malkevitch Feb 19 '11 at 1:39
  • 1
    $\begingroup$ Truncation is a natural operation on polytopes but I am not sure this is necessarily a good name for something more general. Another natural operation polytopes is an edge shave. On a 3-valent 3-polytope this replaces an edge by a 4-gon. $\endgroup$ – Joseph Malkevitch Feb 19 '11 at 16:04
23
$\begingroup$

Along with the already-given answers stating the existence of two graphs G1≠G2 for which T(G1)=T(G2), there is also a different problem: there exist pairs G1=G2 for which T(G1)≠T(G2). This is because the transformation depends not just on the isomorphism class of G, but also on the cyclic ordering of the edges around each vertex of G.

Edited to add an example based on Mark Reitblatt's comment: enter image description here

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You are saying $T$ is not well-defined (for canonical graph definitions), which renders the question ill-posed. $\endgroup$ – Raphael Feb 18 '11 at 19:47
  • $\begingroup$ @David Eppstein: I can not understand anything. Would you please elaborate? Perhaps with an example. Please. $\endgroup$ – Pratik Deoghare Feb 18 '11 at 20:37
  • 4
    $\begingroup$ @TheMachineCharmer Consider a node with 4 edges. When you split it into 4 nodes, you have to make a choice about which new node gets which old edge. This choice will impose an (adjacency) ordering on the new nodes that didn't exist on the old edges. Try it with a node that's connected to 4 different subgraphs, A B C and D. Is the A node adjacent to the B node? Depends on the ordering. But in the old graph, all the edges from this node were adjacent. $\endgroup$ – Mark Reitblatt Feb 18 '11 at 21:29
  • 1
    $\begingroup$ Now its clear to me. btw which software are you using for making these graphs? $\endgroup$ – Pratik Deoghare Feb 19 '11 at 5:24
  • 2
    $\begingroup$ I think labels would actually be more confusing, because there is more than one way to correctly label each graph, so the labels would add information not already present in the isomorphism instance. $\endgroup$ – David Eppstein Feb 19 '11 at 17:06
9
$\begingroup$

The main problem is that Statement I is false, as @Marek just said. There are different graphs transformed into the same graph.

For a concrete example, both (a) tetrahedron (double edges) and (b) octahedron transformed into (c) truncated octahedron.

(a) (b) (c)

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Good! But (b) has multiple edges between its nodes. How about graphs without multiple edges between nodes? Are there families of graphs for where this could work? $\endgroup$ – Pratik Deoghare Feb 18 '11 at 17:46
  • 1
    $\begingroup$ Also, (a) has 6 nodes and (b) has only 4 nodes. In the algorithm only graphs with same number of vertices and edges will be allowed. Because we can discard them in polynomial time. I am sorry I should have specified this earlier. $\endgroup$ – Pratik Deoghare Feb 18 '11 at 18:07
  • 1
    $\begingroup$ In its "second level", (c) has some nodes of degree two. I can not see wether it remains a counterexample after fixing (c). $\endgroup$ – Raphael Feb 18 '11 at 19:58
  • $\begingroup$ @Raphael: Sorry some of the edges are misdrawn. I'll fixed it soon. @TheMachineCharmer: I guess we can construct conunterexamples with larger faces. Update soon! $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 19 '11 at 5:20
  • $\begingroup$ I cannot find any concrete examples with equal number of nodes and without multiple edges. And currently I believe that the main obstacle to the method is the one described by David. Maybe after new concrete examples founded I'll revise my answer. $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 21 '11 at 13:45
5
$\begingroup$

Your Statement I is not true. You can have two non-isomorphic graphs G1, G2 with T(G1), T(G2) isomorphic. Basically, the problem is that there is no reason why isomorphisms between T(G) graphs should map vertex-cycles into vertex-cycles.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.