The variation of the Randić index with regard to minimum and maximum degree

详细信息    查看全文

• 作者：Milica Milivojević ; Ljiljana Pavlović ; ^{pavlovic@kg.ac.rs}
• 关键词：Simple graphs with given minimum degree ; Variation of the Randić index ; Combinatorial optimization ; Quadratic programming
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：286-293
• 全文大小：436 K
• 卷排序：217

文摘

The variation of the Randić index R′(G)R′(G) of a graph GG is defined by R′(G)=∑uv∈E(G)1max{d(u),d(v)}, where d(u)d(u) is the degree of vertex uu and the summation extends over all edges uvuv of GG. Let G(k,n)G(k,n) be the set of connected simple nn-vertex graphs with minimum vertex degree kk. In this paper we found in G(k,n)G(k,n) graphs for which the variation of the Randić index attains its minimum value. When k≤n2 the extremal graphs are complete split graphs Kk,n−k∗, which have only vertices of two degrees, i.e. degree kk and degree n−1n−1, and the number of vertices of degree kk is n−kn−k, while the number of vertices of degree n−1n−1 is kk. For k≥n2 the extremal graphs have also vertices of two degrees kk and n−1n−1, and the number of vertices of degree kk is n2. Further, we generalized results for graphs with given maximum degree.