Affordable Access

Publisher Website

Tree codes that preserve increases and degree sequences

Discrete Mathematics
Publication Date
DOI: 10.1016/0012-365x(91)90138-r


Abstract We define a bijection from the set n of rooted Cayley's trees with n vertices to the set [1, n] n−1 of words of n − 1 letters written with the alphabet [1, n]. This code has three remarkable properties: (1) As in Prüfer's code [1], the degree of every vertex is visible in the word m T = m T (1)… m T ( n−1) coding the tree T. More precisely, if d i denotes the degree of the vertex i: If i is the root of T, then i appears d i times in m T . If not, then i appears d i − 1 times in m T . (2) For any rooted tree, increasing (or decreasing) edges can be defined in the following way: let ( i,j) be an edge of T such that the minimal path joining i to the root passes through j; then the edge ( i,j) is said to be increasing if j> i (and decreasing if j< i) [2]. In other words, if c is the contraction representing T, the edge ( i, c( i)) is increasing if c( i)> i. We prove that the set of letters i in m T such that m T ( i)> i corresponds to the set of increasing edges of T. c( i)> i⇔ m T ( i)> i. (3) From the code m T one derives a code m( T) for Cayley's trees which ‘preserves’ degrees and increases of edges. The code m( T) can be defined independently of m T and therefore from it one derives a bijective proof of Cayley's formula [6]. These properties yield new generating functions. The bijections generalize the classic bijection between permutations linking cycles to outstanding elements [4] (while the bijections of Egecioglu and Remmel [2], which have similar properties, may be viewed as variants of Joyal's code [5]).

There are no comments yet on this publication. Be the first to share your thoughts.