Timeline for What is the complexity of computing isomorphism of two non-regular graphs?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 7 at 23:00 | comment | added | David Roberson | 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. | |
| Mar 7 at 12:44 | comment | added | Eauriel | That makes sense, thank you for a clarification! | |
| Mar 7 at 12:02 | comment | added | Gordon Royle | 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. | |
| S Mar 7 at 11:27 | review | First questions | |||
| Mar 7 at 13:17 | |||||
| S Mar 7 at 11:27 | history | asked | Eauriel | CC BY-SA 4.0 |