Enumeration of labelled (k,m)-trees

DOI10.1006/JCTA.1998.2916MaRDI QIDQ1284483zbMATH OpenOpenAlexFDO

Authors Oleg Pikhurko

Publication date 19 August 1999

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcta.1998.2916

zbMATH Keywords

tree

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30)

Review text

A \(k\)-graph consists of a set of labelled vertices plus a collection of \(k\)-tuples of vertices called edges. Such a graph is a \((k,m)\)-tree if it can be obtained from a single edge by successively adding edges where each new edge consists of \(k-m\) new vertices and \(m\) vertices already belonging to some edge. The author derives an explicit formula for the number of \((k,m)\)-trees with \(e\) edges. When \(k=m+1\) the formula reduces to a formula given earlier by \textit{L. W. Beineke} and \textit{R. E. Pippert} [J. Comb. Theory 6, 200-205 (1969; Zbl 0175.20904)].

Recommendations

• Enumeration of K-trees and applications
• How to count k-paths
• scientific article; zbMATH DE number 4103086
• On the number of spanning trees of \(K_ n\) and \(K_{m,n}\)
• \(\Gamma \)-species and the enumeration of \(k\)-trees

Cites work

• A coding algorithm for Rényi trees
• Cayley's formula for multidimensional trees
• Enumerating k-trees
• Higher-dimensional tree structures. I
• scientific article; zbMATH DE number 4070934 (Why is no real title available?)
• scientific article; zbMATH DE number 3666827 (Why is no real title available?)
• scientific article; zbMATH DE number 3329638 (Why is no real title available?)
• The number of labeled k-dimensional trees
• The number of labeled k-trees

Cited in

(14)

• Enumeration of K-trees and applications
• Enumeration of \(m\)-ary cacti
• Labelled and unlabelled enumeration of k-gonal 2-trees
• The number of m-Husimi trees fixed by a permutation of the vertices
• Labelled trees and factorizations of a cycle into transpositions
• A generalized enumeration of labeled trees and reverse Prüfer algorithm
• Counting unlabeled \(k\)-trees
• Finitely labeled generating trees and restricted permutations
• Counting special families of labelled trees
• scientific article; zbMATH DE number 3843798 (Why is no real title available?)
• scientific article; zbMATH DE number 501065 (Why is no real title available?)
• How to count k-paths
• On the number of labeled k-arch graphs
• \(\alpha\)-labeling number of trees

This page was built for publication: Enumeration of labelled \((k,m)\)-trees

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