The asymptotic value of the Randić index for trees

DOI10.1016/J.AAM.2010.10.008MaRDI QIDQ550268zbMATH OpenOpenAlexFDO

Authors Yiyang Li, Xueliang Li

Publication date 8 July 2011

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.4810

zbMATH Keywords

(General) Randić indexasymptotic valueaverage distancedouble-stargenerating functionnormal distributiontree

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Trees (05C05) Distance in graphs (05C12) Enumeration in graph theory (05C30) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Abstract: Let $mathcal{T}_n$ denote the set of all unrooted and unlabeled trees with $n$ vertices, and $(i,j)$ a double-star. By assuming that every tree of $mathcal{T}_n$ is equally likely, we show that the limiting distribution of the number of occurrences of the double-star $(i,j)$ in $mathcal{T}_n$ is normal. Based on this result, we obtain the asymptotic value of Randi'c index for trees. Fajtlowicz conjectured that for any connected graph the Randi'c index is at least the average distance. Using this asymptotic value, we show that this conjecture is true not only for almost all connected graphs but also for almost all trees.

Recommendations

• Relation between Randić index and average distance of trees
• The asymptotic value of the zeroth-order Randić index and sum-connectivity index for trees
• Limit laws for the Randić index of random binary tree models
• On the Randić index of graphs
• Trees with maximum general Randić index

Cites work

• Graphs of extremal weights
• scientific article; zbMATH DE number 986989 (Why is no real title available?)
• scientific article; zbMATH DE number 5259316 (Why is no real title available?)
• scientific article; zbMATH DE number 3419161 (Why is no real title available?)
• On conjectures of Graffiti
• On the Asymptotic Behavior of Degrees of Vertices in a Random Graph
• On the average Wiener index of degree-restricted trees
• Paths in graphs
• Pattern distribution in various types of random trees
• The distribution of degrees in a large random tree
• The distribution of nodes of given degree in random trees
• The Distribution of Patterns in Random Trees
• The number of trees

Cited in

(4)

• Limit laws for the Randić index of random binary tree models
• scientific article; zbMATH DE number 7062210 (Why is no real title available?)
• The asymptotic value of the zeroth-order Randić index and sum-connectivity index for trees
• The asymptotic number of non-isomorphic rooted trees obtained by rooting a tree

Describes a project that uses

Uses Software

• GRAFFITI

This page was built for publication: The asymptotic value of the Randić index for trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q550268)