The generalized Randić index of trees

✍ Scribed by Paul Balister; Béla Bollobás; Stefanie Gerke

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 241 KB
• Volume: 56
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20267

✦ Synopsis

Abstract

The generalized Randić; index ${R}_{-\alpha}(T)$ of a tree T is the sum over the edges ${u}{v}$ of T of $(d(u)d(v))^{-\alpha}$ where ${d}(x)$ is the degree of the vertex x in T. For all $\alpha > 0$, we find the minimal constant $\beta_{0}=\beta_{0}(\alpha)$ such that for all trees on at least 3 vertices, ${R}_{-\alpha}(T)\leq\beta_{0}(n+1)$, where ${n}={n}(T)= |{V}(T)|$ is the number of vertices of T. For example, when $\alpha=1, \beta_{0}={15\over 56}$. This bound is sharp up to the additive constant—for infinitely many n we give examples of trees T on n vertices with ${R}_{-\alpha}(T)\geq \beta_{0}(n- 1)$. More generally, fix $\gamma > 0$ and define $\tilde {n}=(n- n_{1})+\gamma {n}_{1}$, where ${n}_{1}= {n}_{1}(T)$ is the number of leaves of T. We determine the best constant $\beta_{0}=\beta_{0}(\alpha, \gamma)$ such that for all trees on at least 3 vertices, ${R}_{-\alpha}(T)\leq \beta_{0}(\tilde {n}+{1})$. Using these results one can determine (up to ${o}(n)$ terms) the maximal Randić; index of a tree with a specified number of vertices and leaves. Our methods also yield bounds when the maximum degree of the tree is restricted. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 270–286, 2007