-1
$\begingroup$

Let the Graph Isomorphism Problem be the problem to decide whether there is a one-to-one mapping between the vertices of two graphs that preserves the edge relations.

Let the Graph Isomorphism Problem for Connected Graphs be the problem to decide whether there is a one-to-one mapping between the vertices of two connected graphs that preserves the edge relations.

Is there a polynomial time reduction from the Graph Isomorphism Problem to the Graph Isomorphism Problem for connected graphs? How can I prove it?

$\endgroup$

closed as off-topic by Jeffε, Kaveh Dec 1 '13 at 18:56

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Jeffε, Kaveh
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ This is not a research-level question so is off-topic, here. Computer Science Stack Exchange would have been a more appropriate place to ask but, since the question has already been answered, there's no need to repost there. $\endgroup$ – David Richerby Nov 22 '13 at 18:31
  • 2
    $\begingroup$ Sorry. The research-level criterion for questions should be put into the "How to ask" box on the ask page to avoid this from happening. $\endgroup$ – Nils Wisiol Nov 22 '13 at 19:02
  • 2
    $\begingroup$ Good point. I've suggested it on meta. $\endgroup$ – David Richerby Nov 22 '13 at 19:16
  • $\begingroup$ The "research-level" requirement is now mentioned both in the "How to ask" box and the greyed out text that sits in the subject line before it's edited. $\endgroup$ – David Richerby Nov 24 '13 at 9:27
2
$\begingroup$

What about the following simple reduction: given graphs $G$ and $H$, let $G' = G * g$ and $H' = H * h$, where $X * x$ is obtained from $X$ by adding a new vertex $x$ and all edges between $x$ and all vertices in $X$ (so, $x$ is universal in $X * x$).

Then $G$ and $H$ are isomorphic iff $G'$ and $H'$ are isomorphic. Note that, in all cases, $G'$ and $H'$ are connected.

$\endgroup$
  • $\begingroup$ Your reduction doesn't require that $G$ and $H$ have no universal vertex (which is good, since you can't actually assume that). $\endgroup$ – David Richerby Nov 22 '13 at 18:28
  • $\begingroup$ Oh, yes, you are right. $\endgroup$ – user13667 Nov 22 '13 at 18:35
  • $\begingroup$ We don't answer undergraduate homework level questions on this site. $\endgroup$ – Kaveh Dec 1 '13 at 18:57

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