So a canonical labelling of a graph G is a function CL(G) that maps each vertex to a numerical label. Sorry if my definitions are a bit obvious or clumsy, by the way. For every isomorphic graph G', CL(G) = CL(G').

Now, I'm actually dealing here with spanning trees of the graph, and spanning subtrees. The tree T that spans G is rooted at a particular vertex, and the labelling of this tree may not be canonical for the whole graph.

My question, then is this : if you label a subtree of a particular spanning tree, will its labels sometimes not be a subsequence of the labels of the tree? Even less formally : is the local order defined by (any) function CL likely to be inconsistent with the global order.

Of course, there could be graphs for which subtrees of certain depths are consistent for particular vertices. By consistent I mean subsequence as [0,2,1] is a subsequence of [0,2,1,3,4].

  • 1
    $\begingroup$ I am not sure what a "subsequence" means in this context? Could you perhaps give examples of canonical labellings that have vs. do not have this property? $\endgroup$ – Jukka Suomela Feb 17 '11 at 20:54

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.