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
    Commented Jul 4, 2012 at 9:55
  • $\begingroup$ one process we choice one cycle. $\endgroup$
    – Pham Hung Quy
    Commented 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
    Commented 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
    Commented 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
    Commented Aug 26, 2021 at 1:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .