On the Randić index

DOI10.1016/S0012-365X(02)00256-XMaRDI QIDQ5917418zbMATH OpenFDO

Authors C. Delorme, Odile Favaron, Dieter Rautenbach

Publication date 2 December 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(02)00256-X

zbMATH Keywords

degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Applications of graph theory (05C90)

Review text

The Randić index \(R(G)\) of a graph \(G\) is the sum of \((d(u) d(v))^{-1/2}\) over all edges of \(G\), where \(d(u)\) denotes the degree of vertex \(u\). \textit{B. Bollobás} and \textit{P. Erdős} [Ars Comb. 50, 225-233 (1998; Zbl 0963.05068)] showed that if the minimum degree \(\delta(G)\) of the vertices of \(G\) is at least one, then \(R(G)\geq \sqrt{n-1}\) with equality holding if and only if \(G\) is a star. The authors of the present paper show that if \(\delta(G)\geq 2\), then \(R(G)\geq \sqrt{2}(n- 2)/\sqrt{n-1}+1/(n-1)\) with equality holding if and only if \(G\) is the complement of the graph consisting of a complete graph with \(n-2\) vertices plus two isolated vertices. They also show that if \(\delta(G)\geq d\geq 1\) and \(G\) is triangle-free, then \(R(G)\geq \sqrt{d(n-d)}\) with equality holding if and only if \(G\) is the complete \(d\) by \(n-d\) bipartite graph.

Recommendations

Cited in

(50)

This page was built for publication: On the Randić index

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