A New Formula for the Hitting Time Index of Broom Graphs

Bn,d is a tree with n vertices consisting of a path Pd and n−d leaves attached to one of its endpoints. The hitting time index HT(Bn,d) is, as for every tree, always an integer, thus forming a two-dimensional integer array HT(Bn,d):n≥3,2≤d≤n−1. In this paper we reveal a unique property of this array: for a fixed number of leaves k=n−d and sufficiently large n, HT(Bn,n−k) can be represented by a quartic quasi-polynomial in n, whereas it was shown earlier that for a fixed path length d and n≥4d−8 the same array is represented by a cubic polynomial in n. In other words, one and the same integer array possesses two fundamentally different polynomial representations—cubic and quartic—depending on which parameter is fixed. This property allows us to connect HT(Bn,d) with well-known integer sequences in the On-Line Encyclopedia of Integer Sequences. We prove an explicit quartic formula for HT(Bn,n−k) for all k≥1 and n≥n0(k), thereby extending the range of large d for which a closed polynomial form is known, and at the same time unifying earlier partial results for small values of k. As an application, we prove the strict monotonicity of the sequence HT(Bn,d) as a function of d in the large-d regime and complete the chain of inequalities up to the extreme case d=n−1 (the path Pn).