1
$\begingroup$

Suppose I want to test an algorithm for graph isomorphism check.

Starting from a given graph, I would do a random permutation of vertices to build the second graph.

Is there a way of making another isomorphic graph that is "more difficult" to check?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ No, because given any labelling of a graph you can make a random labelling of that. So every labelling is equally difficult. That doesn't mean a particular algorithm will take the same time for each labelling. $\endgroup$
    – Brendan McKay
    Sep 11, 2021 at 14:51
  • 1
    $\begingroup$ Maybe it's more interesting to ask for a non-isomorphic graph that is difficult to check? $\endgroup$
    – Gerry Myerson
    Sep 12, 2021 at 1:38
  • 1
    $\begingroup$ @Gerry Myerson yes, right. $\endgroup$
    – BillyJoe
    Sep 12, 2021 at 6:47

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .