Let $G$ - be an undirected graph (not necessary connected) with up to $n=9$ vertices, and $[G]$ - a set of all graphs isomorphic to $G$. Is there a decent algorithm for a function $f: [G] \to [G]$ which acts as follows: graphs $G$ and $H$ are isomorphic iff $f(G) = f(H)$. Thus $f(G)$ finds a representative graph for $[G]$.

I understand that this problem can be solved in $O(n!)$ time. In general this can be optimized by sorting vertices by the number of adjacent edges. Due to considerably small number of vertices, it is possible to generate some tables and other helper structures beforehand, but I just can't figure out an algorithm which would benefit of these pre-cached structures.

  • $\begingroup$ This is the problem of determining a canonical form (or labelling) for a graph. The pre-cached structures sound like graph invariants - if two graphs have different invariants then they cannot be isomorphic. For example, the degree sequence is such an invariant. $\endgroup$ – gilleain Jun 27 '18 at 15:46
  • $\begingroup$ Thank you very much. Now I know the keywords to google for :) $\endgroup$ – Ordev Agens Jun 29 '18 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.