2017/10/23 by Sally Picciotto, Picciotto, Sally · 4 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1710.08463
openalex publication_date 2017/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We construct bijections giving three "codes" for trees. These codes follow naturally from the Matrix Tree Theorem of Tutte and have many advantages over the one produced by Prufer in 1918. One algorithm gives explicitly a bijection that is implicit in Orlin's manipulatorial proof of Cayley's formula (the formula was actually found first by Borchardt). Another is based on a proof of Knuth. The third is an implementation of Joyal's pseudo-bijective proof of the formula, and is equivalent to one previously found by Egecioglu and Remmel. In each case, we have at least two algorithms, one of which involves hands-on manipulations of the tree while the other involves a combinatorial and linear algebraic manipulation of a matrix.