Special canonical labelling functions

28 Views Asked by At

Given a graph class $\mathcal{G}$, a function $\mathcal{f}$ defined on $\mathcal{G}$ is said to compute canonical forms of $\mathcal{G}$ if it satisfies the following:

$$\forall G,H \in \mathcal{G} : if G\cong H \equiv f(G) = f(H)$$ $$\forall G\in \mathcal{G}: f(G) \cong G$$

Now there are some function for which this problem is hard and easy for some others. What are the examples of $f$, for which above problem is easy to solve.