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

Milica Milivojevic, Ljiljana Pavlovic

Published 2016-02-11Version 1

The variation of the Randi\'c index $ R'(G) $ of a graph $G$ is defined by\ $R(G) = \sum_{uv \in E(G)}\frac 1{\max \{d(u) d(v)\}}$, where $d(u)$ is the degree of vertex $u$ and the summation extends over all edges $uv$ of $G$. Let $G(k,n)$ be the set of connected simple $n$-vertex graphs with minimum vertex degree $k$. In this paper we found in $G(k,n)$ graphs for which the variation of the Randi\'c index attains its minimum value. When $k \leq \frac n2$ the extremal graphs are complete split graphs $K_{k,n-k}^*$, which only vertices of two degrees, i.e. degree $k$ and degree $n-1$, and the number of vertices of degree $k$ is $n-k$, while the number of vertices of degree $n-1$ is $k$. For $k \geq \frac n2$ the extremal graphs have also vertices of two degrees $k$ and $n-1$, and the number of vertices of degree $k$ is $\frac n2$. Further, we generalized results for graphs with given maximum degree.