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

被引:14
作者
Suil, O. [1 ]
Shi, Yongtang [2 ,3 ]
机构
[1] State Univ New York, Dept Appl Math & Stat, Incheon 21985, South Korea
[2] Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China
[3] Nankai Univ, LPMC, Tianjin 300071, Peoples R China
基金
中国国家自然科学基金;
关键词
Randic index; Maximum degree; Minimum degree; VARIABLE NEIGHBORHOOD SEARCH; EXTREMAL GRAPHS; CONNECTIVITY INDEX; CONJECTURES; DIAMETER;
D O I
10.1016/j.dam.2018.03.064
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The Randic index of a graph G, written R(G), is the sum of 1/root d(u)d(v) over all edges uv in E(G). Let d and D be positive integers d < D. In this paper,(WT) prove that if G is a graph with minimum degree d and maximum degree D, then R(G) >= root dD/d+Dn; 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) <= n/2 - Sigma(D-1)(i=d) 1/2 (1/root i - 1/root i+1)(2) : it is sharp for infinitely many n, and we characterize when equality holds in the bound. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码:111 / 115
页数:5
相关论文
共 20 条
[1]  
Aouchiche M, 2006, MATCH-COMMUN MATH CO, V56, P541
[2]  
Aouchiche M, 2007, MATCH-COMMUN MATH CO, V58, P83
[3]   On a conjecture about the Randic index [J].
Aouchiche, Mustapha ;
Hansen, Pierre .
DISCRETE MATHEMATICS, 2007, 307 (02) :262-265
[4]   The connectivity index of a weighted graph [J].
Araujo, O ;
de la Pena, JA .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1998, 283 (1-3) :171-177
[5]   Extremal graphs for weights [J].
Bollobás, B ;
Erdos, P ;
Sarkar, A .
DISCRETE MATHEMATICS, 1999, 200 (1-3) :5-19
[6]  
Bollobás B, 1998, ARS COMBINATORIA, V50, P225
[7]   Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system [J].
Caporossi, G ;
Hansen, P .
DISCRETE MATHEMATICS, 2000, 212 (1-2) :29-44
[8]   Graphs with maximum connectivity index [J].
Caporossi, G ;
Gutman, I ;
Hansen, P ;
Pavlovic, L .
COMPUTATIONAL BIOLOGY AND CHEMISTRY, 2003, 27 (01) :85-90
[9]   On the Randic index [J].
Delorme, C ;
Favaron, O ;
Rautenbach, D .
DISCRETE MATHEMATICS, 2002, 257 (01) :29-38
[10]   Randic index and the diameter of a graph [J].
Dvorak, Zdenek ;
Lidicky, Bernard ;
Skrekovski, Riste .
EUROPEAN JOURNAL OF COMBINATORICS, 2011, 32 (03) :434-442