Paths vs. stars in the local profile of trees

2015/12/21 by Éva Czabarka, László A. Székely, Czabarka, Éva +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1512.06526

arxiv created 2016/02/13 · arxiv updated 2016/02/16

Abstract

The aim of this paper is to provide an affirmative answer to a recent question by Bubeck and Linial on the local profile of trees. For a tree T, let p^(k)₁(T) be the proportion of paths among all k-vertex subtrees (induced connected subgraphs) of T, and let p^(k)₂(T) be the proportion of stars. Our main theorem states: if p^(k)₁(T_n) → 0 for a sequence of trees T₁,T₂,… whose size tends to infinity, then p^(k)₂(T_n) → 1. Both are also shown to be equivalent to the statement that the number of k-vertex subtrees grows superlinearly and the statement that the (k-1)th degree moment grows superlinearly.

Related

• On the local profiles of trees
• On paths, stars and wyes in trees
• The Proportion of Trees that are Linear
• Limbs and Cospectral Vertices in Trees
• Extrema of local mean and local density in a tree