0
$\begingroup$

Regular graphs are the graphs in which the degree of each vertex is the same. Much research has gone into investigating isomorphism of regular graphs, and we know that computing isomorphism for regular graphs is GI-complete problem. On the other hand, do we know what happens if we are guaranteed that the two graphs are non-regular? What is the (theoretical) computational complexity of computing isomorphism of two non-regular graphs (obviously, having the same degree sequence)? Is this problem polynomial? If so, what is the corresponding complexity class? Please provide also references. Thank you!

Improve this question
$\endgroup$
3
  • 7
    $\begingroup$ If you could determine if two non-regular graphs were isomorphic in polynomial time, then you could do the same for regular graphs - stick a pendant edge onto a vertex of one graph, then do the same for each vertex in turn of the second graph. Then after $n$ runs of the non-regular algorithm you would have an answer. $\endgroup$
    – Gordon Royle
    Commented Mar 7 at 12:02
  • $\begingroup$ That makes sense, thank you for a clarification! $\endgroup$
    – Eauriel
    Commented Mar 7 at 12:44
  • 1
    $\begingroup$ You could ask about asymmetric graphs (graphs whose only automorphism is the identity) instead of non-regular graphs. I think this might be an open problem. $\endgroup$
    – David Roberson
    Commented Mar 7 at 23:00

0

Reset to default

You must log in to answer this question.