0
$\begingroup$

Sorry if the following are stupid questions (i do not know much about the graph theory).

1. Motivation

we do not know the graph isomorphism problem in class P or NP complete and it is P in the case trees (see http://en.wikipedia.org/wiki/Graph_isomorphism_problem).

2. Transformation a graph to tree

Let $G$ be a simple connect graph with $v$ vertices and $e$ edges. We consider the following process:

Process: If $G$ is not a tree we will have a cycle in $G$, called $C_k$ with vertices (assume that) $v_1,...,v_k$. Then

  • We add a new vertex $w$ to $G$
  • delete $k$ edges of $C_k$: $(v_1,v_2),...,(v_k, v_1)$.
  • Add $k$ edges $(w,v_1),...,(w,v_k)$ to the graph.

We obtain a new graph $G'$ with $v+1$ vertices and $e$ edges.

Theorem. Applying the above process $v - e + 1$ times we get a tree $T$.

Notice that we may get many trees by different processes.

Question 1. Assume that we always choice $C_k$ such that $k$ as small as possible. Is it true that every tree we obtain are isomorphism?

I do not know this question true or false. In the case we have a negative in general, which condition it is true?

3. The graph isomorphism problem

In the case Question 1 has an affirmative answer for each $G$ we get a tree $T(G)$ (up to an isomorphism).

Question 2. Assume that $G$ and $H$ are simple connect graph with same number of vertices, edges, degrees of vretex,... (we can need more condition which easy to check). Whether $G$ and $H$ are isomorphism iff $T(G)$ and $T(H)$ are isomorphism?

$\endgroup$

1 Answer 1

6
$\begingroup$

If two cycles of minimum length have a common edge, then it matters which is chosen. Try two triangles with a common edge, plus one more vertex joined to an apex of one of the triangles.

$\endgroup$
5
  • $\begingroup$ we choice one of them and get a new graph. $\endgroup$ Jul 4, 2012 at 9:55
  • $\begingroup$ one process we choice one cycle. $\endgroup$ Jul 4, 2012 at 9:57
  • $\begingroup$ If you try the different possible processes with the graph suggested by Brendan, you will see that the answer to question 1 is no. $\endgroup$
    – nvcleemp
    Jul 4, 2012 at 10:20
  • $\begingroup$ @BrendanMcKay but what about if we process both triangles? When recostructing, we will know about the doubled common edge, that we can simplify. $\endgroup$ Aug 24, 2021 at 22:27
  • 1
    $\begingroup$ @BillyJoe The order of processing the cycles matters in general. There is also another problem: when the cycle is long there is more than one graph that gives the same result. $\endgroup$ Aug 26, 2021 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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