×

On the Randić index of graphs. (English) Zbl 1417.05033

Summary: For a given graph \(G = (V, E)\), the degree mean rate of an edge \(u v \in E\) is a half of the quotient between the geometric and arithmetic means of its end-vertex degrees \(d(u)\) and \(d(v)\). In this note, we derive tight bounds for the Randić index of \(G\) in terms of its maximum and minimum degree mean rates over its edges. As a consequence, we prove the known conjecture that the average distance is bounded above by the Randić index for graphs with order \(n\) large enough, when the minimum degree \(\delta\) is greater than (approximately) \(\varDelta^{\frac{1}{3}}\), where \(\varDelta\) is the maximum degree. As a by-product, this proves that almost all random (Erdős-Rényi) graphs satisfy the conjecture.

MSC:

05C07 Vertex degrees
05C40 Connectivity
05C12 Distance in graphs
05C80 Random graphs (graph-theoretic aspects)

References:

[1] Beezer, R. A.; Riegsecker, J. E.; Smith, B. A., Using minimum degree to bound average distance, Discrete Math., 226, 365-371 (2001) · Zbl 0959.05038
[2] Bollobás, B., Degree sequences of random graphs, Discrete Math., 33, 1-19 (1981) · Zbl 0447.05038
[3] Bollobás, B.; Erdős, P., Graphs of extremal weights, Ars Combin., 50, 225-233 (1998) · Zbl 0963.05068
[4] Caporossi, G.; Hansen, P., Variable neighborhood search for extremal graphs 1: The AutographiX system, Discrete Math., 212, 29-44 (2000) · Zbl 0947.90130
[5] Caporossi, G.; Gutman, I.; Hansen, P.; Pavlović, L., Graphs with maximum connectivity index, Comput. Biol. Chem., 27, 85-90 (2003)
[6] Fajtlowicz, S., On conjectures of Graffiti, Discrete Math., 72, 113-118 (1988) · Zbl 0711.68081
[7] Li, X.; Shi, Y., Randić index, diameter and average distance, MATCH Commun. Math. Comput. Chem., 64, 425-431 (2010) · Zbl 1265.05122
[8] Pavlović, L.; Gutman, I., Graphs with extremal connectivity index, Novi Sad J. Math., 31, 53-58 (2001) · Zbl 1274.05246
[9] Randić, M., Characterization of molecular branching, J. Am. Chem. Soc., 97, 6609-6615 (1975)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.