Sharp bounds for the Randic index of graphs with given minimum and maximum degree

2017/05/17 by O, Suil, Shi, Yongtang · 1 citation
#05C07 #05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1705.05963

Abstract

The Randi' c index of a graph G, written R(G), is the sum of \frac 1√(d(u)d(v)) over all edges uv in E(G). %let R(G)=∑_{uv ∈ E(G)} \frac 1√(d(u)d(v)), which is called the Randi' c index of it. Let d and D be positive integers d < D. In this paper, we prove that if G is a graph with minimum degree d and maximum degree D, then R(G) ≥ (√(dD))/(d+D)n; equality holds only when G is an n-vertex (d,D)-biregular. Furthermore, we show that if G is an n-vertex connected graph with minimum degree d and maximum degree D, then R(G) ≤ \frac n2- ∑_i=d^D-1\frac 12 ( \frac 1√(i) - \frac 1√(i+1))²; it is sharp for infinitely many n, and we characterize when equality holds in the bound.

Cited by

• A sharp Randić bound for König--Egerváry graphs and a conjecture of Aouchiche, Hansen, and Zheng

Related

• The extremal generalised Randić index for a given degree range
• The variation of the Randic index with regard to minimum and maximum\n degree
• Some Bounds on Zeroth-Order General Randić Index
• First and Second Maximum of Randić Index Among all k-Cyclic Graphs of a Given Order
• Randić index, diameter and the average distance