The asymptotic number of occurrences of a subtree in trees with bounded maximum degree and an application to the Estrada index

preprint2010arXivOpen access

Abstract

Let TnΔ\mathcal {T}^Δ_n denote the set of trees of order nn, in which the degree of each vertex is bounded by some integer ΔΔ. Suppose that every tree in TnΔ\mathcal {T}^Δ_n is equally likely. For any given subtree HH, we show that the number of occurrences of HH in trees of TnΔ\mathcal {T}^Δ_n is with mean (μH+o(1))n(μ_H+o(1))n and variance (σH+o(1))n(σ_H+o(1))n, where μHμ_H, σHσ_H are some constants. As an application, we estimate the value of the Estrada index EEEE for almost all trees in TnΔ\mathcal {T}^Δ_n, and give an explanation in theory to the approximate linear correlation between EEEE and the first Zagreb index obtained by quantitative analysis.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.