A coding algorithm for Rényi trees
type: Item
instance of: scholarly article
title: A coding algorithm for Rényi trees
zbMATH Open document ID: 0773.05039
DOI: 10.1016/0097-3165(93)90021-Y
author: William Y. C. Chen
published in: Journal of Combinatorial Theory. Series A
publication date: 1993-05-23T00:00:00Z
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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 165155
zbMATH Keywords: Rényi trees
zbMATH Keywords: \(k\)-trees
zbMATH Keywords: bijection
zbMATH Keywords: sequences
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: Q5596092
cites work: The number of labeled k-dimensional trees
cites work: Onq-trees
cites work: A general bijective algorithm for trees.
cites work: Q3803143
cites work: Enumerating k-trees
cites work: Cayley's formula for multidimensional trees
cites work: On acyclic simplicial complexes
cites work: The number of labeled k-trees
cites work: Q5616724
cites work: On the number of labeled 2-trees
cites work: Q5599571
cites work: Q5607734
cites work: On simple characterizations of k-trees
cites work: Q3960734
description: scientific article; zbMATH DE number 165155