A coding algorithm for Rényi trees

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

The author considers \(k\)-trees with \(n\) labelled nodes \(1,2,\dots,n\) constructed as follows: start with a complete \(k\)-graph with nodes \(n- k+1,\dots,n\) and successively join a new node to \(k\) nodes already joined to each other. He shows that there is a bijection between these \(k\)-trees with \(n\) nodes and certain doubly labelled rooted trees with \(n-k+1\) nodes and one between these latter trees and certain doubly labelled forests of trees of height one. This ultimately gives rise to a bijection between \(k\)-trees with \(n\) labelled nodes and sequences of length \(n-k+1\) over an alphabet of \(k(n-k)+1\) elements. Some applications of these bijections are discussed.

Recommendations

Cited in

(17)

This page was built for publication: A coding algorithm for Rényi trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1207762)