-1
$\begingroup$

Suppose you are given two graphs $G_1$ and $G_2$ and are promised that both are twin free. Is the problem of determining if they are isomorphic graph isomorphism hard? I am curious for the cases of simple as well as non-simple directed graphs.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ What is "twin free"? $\endgroup$
    – joro
    Commented Jan 4, 2016 at 13:28
  • 1
    $\begingroup$ @joro I assume twins are pairs of vertices with exactly the same neighbours. And twin free means no two vertices are twins. $\endgroup$
    – Tony Huynh
    Commented Jan 4, 2016 at 19:23

1 Answer 1

Reset to default
6
$\begingroup$

Twins are easy to detect. Equivalence classes of twins can be replaced by single vertices with colours (or attached gadgets if you don't like colours) that encode the multiplicity. So the general case is no harder than the twin-free case.

Improve this answer
$\endgroup$

You must log in to answer this question.

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