DOAJ Open Access 2012

On the number of transversals in random trees

Bernhard Gittenberger Veronika Kraus

Lihat Sumber DOI

Abstrak

We study transversals in random trees with n vertices asymptotically as n tends to infinity. Our investigation treats the average number of transversals of fixed size, the size of a random transversal as well as the probability that a random subset of the vertex set of a tree is a transversal for the class of simply generated trees and for Pólya trees. The last parameter was already studied by Devroye for simply generated trees. We offer an alternative proof based on generating functions and singularity analysis and extend the result to Pólya trees.

Topik & Kata Kunci

Mathematics

Penulis (2)

Bernhard Gittenberger

Veronika Kraus

Format Sitasi

APA MLA BibTeX

Gittenberger, B., Kraus, V. (2012). On the number of transversals in random trees. https://doi.org/10.46298/dmtcs.2990

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.2990

Informasi Jurnal

Tahun Terbit: 2012
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.2990
Akses: Open Access ✓