Enumeration and Bijections of a Class of Labelled Plane Trees and Related Structures

Abstract

In this paper, we introduce and enumerate weakly labelled k-plane trees by number of vertices, occurrences of vertices of a certain type, root degree, label of the eldest child of the root, label of the youngest child of the root, number of leaves, forests and outdegree sequence. Bijections between the set of these trees and the sets of k-ary Husimi graphs, k-plane trees, plane trees where each internal vertex has a given number of leaf children and weakly labelled k-trees are also constructed