Back to Search Start Over

Sub-trees of a random tree

Authors :
Paweł Prałat
Bogumił Kamiński
Source :
Discrete Applied Mathematics. 268:119-129
Publication Year :
2019
Publisher :
Elsevier BV, 2019.

Abstract

Let T be a random tree taken uniformly at random from the family of labelled trees on n vertices. In this note, we provide bounds for c ( n ) , the number of sub-trees of T that hold asymptotically almost surely (a.a.s.). With computer support we show that a.a.s. 1 . 4180538 6 n ≤ c ( n ) ≤ 1 . 4195988 1 n . Moreover, there is a strong indication that, in fact, a.a.s. c ( n ) ≤ 1 . 4180618 3 n .

Details

ISSN :
0166218X
Volume :
268
Database :
OpenAIRE
Journal :
Discrete Applied Mathematics
Accession number :
edsair.doi...........6870231a1609d68fa77675c419531db1