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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ we choice one of them and get a new graph. $\endgroup$
    – Pham Hung Quy
    Jul 4, 2012 at 9:55
  • $\begingroup$ one process we choice one cycle. $\endgroup$
    – Pham Hung Quy
    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$
    – Fabius Wiesner
    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$
    – Brendan McKay
    Aug 26, 2021 at 1:30

Your Answer

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

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