# Minimum Variable Connectivity Index of Trees of a Fixed Order

Authors: Shamaila Yousaf; Akhlaq Ahmad Bhatti; Akbar Ali
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

The connectivity index, introduced by the chemist Milan Randić in 1975, is one of the topological indices with many applications. In the first quarter of 1990s, Randić proposed the variable connectivity index by extending the definition of the connectivity index. The variable connectivity index for graphG is defined as ∑vw∈EGdv+γdw+γ−1/2, where γ is a nonnegative real number, EG is the edge set of G, and dt denotes the degree of an arbitrary vertex t in G. Soon after the innovation of the variable connectivity index, its various chemical applications have been reported in different papers. However, to the best of the authors’ knowledge, mathematical properties of the variable connectivity index, for γ>0, have not yet been discussed explicitly in any paper. The main purpose of the present paper is to fill this gap by studying this topological index in a mathematical point of view. More precisely, in this paper, we prove that the star graph has the minimum variable connectivity index among all trees of a fixed order n, where n≥4.


---

## Body

## 1. Introduction

All the graphs that we discuss in the present study are simple, connected, undirected, and finite. For a graphG=V,E, the number VG is called its order, and EG is the size of G. Neighbor of a vertex v∈VG is a vertex adjacent to v. The set of all neighbors of vertex v of G is denoted by Nv. The number Nv is called the degree of a vertex, v∈G, and it is denoted by dv. If dv=1, then v is called a pendent vertex or a leaf. A graph of order n is called an n-vertex graph. Denote by Pn and Sn the n-vertex path graph and the n-vertex star graph, respectively. The class of all n-vertex trees is denoted by Tn. For the (chemical) graph theoretical notation and terminology that are not defined in this paper, refer to [1, 2].One of the fundamental ideas in CGT (chemical graph theory) is molecular connectivity. Chemical behavior of a compound is dependent upon its structure. QSPR/QSAR (quantitative structure-property/activity relationship) studies are progressive fields of chemical research that focus on the behavior of this dependency. The quantitative relationships are mathematical models that either enable the prediction of a continuous variable (e.g., boiling point andLC50 toxicity) or the classification of a discrete variable (e.g., sweet/bitter and toxic/nontoxic) from structural parameters. Actually, CGT has provided many topological indices that have been and are being used in QSPR/QSAR studies for predicting the physicochemical properties of chemical compounds. Topological indices are those graph invariants that found some applications in chemistry [3–6]. For further details about the topological indices and their applications, refer to [3, 7–11] and the references therein.Molecules can be modeled using graphs in which vertices correspond to atoms of the considered molecules, and the edges correspond to the covalent bonds between atoms [6]. To model the heteroatom molecules, it is better to use the vertex-weighted graphs, which are the graphs whose one or more vertices are distinguished in some way from the rest of the vertices [12]. Let G be a vertex-weighted graph with the vertex set v1,v2,…,vn, and let wibe the weight of the vertex vi for i=1,2,…,n. The augmented vertex-adjacency matrix of G is an n×n matrix denoted by AavG and is defined as AavG=ai,jn×n, where(1)ai,j=1,ifvivj∈EG;wi,ifi=j;0,otherwise.The variable connectivity index [13, 14], proposed by Randić, for graph G is defined as(2)χ1fG=∑vivj∈EG1dvi+widvj+wj.We associate this index’s name with its inventor Randić by calling it as the variable Randić index. This index was actually introduced within the QSPR/QSAR studies of heteroatom molecules. IfG is the molecular graph of a homoatomic molecule, then w1=w2=⋯=wn=γ (say), and hence, the variable Randić index χ1fG becomes(3)χ1fG=vRγG=∑vivj∈EG1dvi+γdvj+γ.In the rest of this paper, we denote this index byRvγ instead of χ1f. Clearly, if we take γ=0, then the invariant RvγG is the classical Randić index [10, 15]. Liu and Zhong [5] showed that the variable Randić index has more flexibility in characterizing polymers, which can lead to simpler correlations with better correlative accuracy. Details about the chemical applications of the variable Randić index can be found in [5, 7, 9, 12, 15–22] and related references listed therein. It needs to be mentioned here that the variable Randić index seems to have more chemical applications than the several well-known variable indices, for example, the indices considered in [23–33]. However, to the best of the authors’ knowledge, mathematical properties of the variable Randić index, for γ>0, have not yet been discussed explicitly in any paper. The main purpose of the present paper is to fill this gap by studying this topological index in a mathematical point of view. Since the trees (that are the connected graphs without cycles) form an important class of graphs both in chemical graph theory as well as in general graph theory, in this paper, we study an extremal problem related to the variable Randić index of the class of trees. We prove that the star graph Sn has the minimum variable Randić index among all trees of a fixed order n, where n≥4.


## 2. Main Result

To establish the main result, we prove a lemma first.Lemma 1.
Ifγ≥0 and s,t≥2, then function f defined as(4)fγ,s,t=s+t−1s+t−1+γ−s−1s+γ−t−1t+γ−s+γt+γ1+γ,is positive-valued.Proof.
We note that the function∂f/∂s is strictly increasing in t on the interval 1,∞ because(5)∂f∂s=s+t−1+γ+s+t−12s+t−1+γ−s+γ−s−12s+γ−t+γ21+γs+γ,∂∂t∂f∂s=31+γt+γs+γ−s+t−1+γ41+γt+γs+γs+t−1+γ+γ4s+t−1+γ3/2>0,where the last inequality holds because(6)γ+1s+γt+γ≥s+γt+γ>s+γ+t+γ−1≥s+t+γ−1.
Also, note that the value of the function∂f/∂s at t=1 is 0, which implies that the function ∂f/∂s is positive-valued for t>1, and hence, function f is strictly increasing in s on the interval 1,∞. Due to the identity fγ,s,t=fγ,t,s, function f is strictly increasing also in t on the interval 1,∞. It holds that fγ,1,t=fγ,t,1=0, and hence, fγ,s,t>0 for all s,t>1 and γ≥0.Transformation 1. Forn≥4, let T be a tree of order n containing at least two nonpendent vertices. Let u∈VT be a vertex of maximum degree, and let NTu=v,u1,u2,…,us−1, where dv≥dui for i=1,2,…,s−1. Also, take NTv=u,v1,v2,…,vt−1. Note that s≥t≥2. We transform T into another tree T´ by removing the edges vv1,vv2,…,vvt−1 and adding the edges uv1,uv2,…,uvt−1.Lemma 2.
LetT and T´ be the trees defined in Transformation 1. For γ≥0, it holds that(7)RvγT´<RvγT.Proof.
By using the definition of the variable Randić index, one has(8)RvγT−RvγT´=∑i=1s−1fs,dui−fs+t−1,dui+∑i=1t−1ft,dvi−fs+t−1,dvi+fs,t−fs+t−1,1,where(9)fa,b=1a+γb+γ.
Equation (8) gives(10)RvγT−RvγT´=∑i=1s−1fs,dui1−fs+t−1,duifs,dui+∑i=1t−1ft,dvi1−fs+t−1,dvift,dvi+fs,t−fs+t−1,1=∑i=1s−1fs,dui1−s+γs+t−1+γ+∑i=1t−1ft,dvi1−t+γs+t−1+γ−11+γs+t−1+γ+1s+γt+γ.
Since the vertexu∈VT has the maximum degree, that is, du=s≥dw for every w∈VT and dv=t≥dui for i=1,2,…,s−1, thus, fs,dui≥fs,t and ft,dvi≥ft,s=fs,t. Hence, equation (10) yields(11)RvγT−RvγT´≥s−1s+γt+γ1−s+γs+t−1+γ+t−1s+γt+γ1−t+γs+t−1+γ−11+γs+t−1+γ+1s+γt+γ=s−1s+γt+γ+t−1s+γt+γ+1t+γs+γ−s−1t+γs+t−1+γ−t−1s+γs+t−1+γ−11+γs+t−1+γ=1s+γt+γs+t−1+γs+t−1s+t−1+γ−s−1s+γ−t−1t+γ−s+γt+γ1+γ.
By using Lemma1 in (11), we get RvγT−RvγT´>0, as desired.
Next result is a direct consequence of Lemma2.Theorem 1.
Forn≥4 and γ≥0, among all trees of a fixed order n, star graph Sn is the unique tree with minimum variable Randić index Rvγ, which is(12)n−1n−1+γ1+γ.
Forγ≥0 and small values of n, we calculate the variable Randić index Rvγ of the trees of order n and find that the value of this index does not exceed from(13)RvγPn=21+γ2+γ+n−32+γ.
This suggests the following conjecture.Conjecture 1.
Forn≥4 and γ≥0, among all trees of a fixed order n, path graph Pn is the unique tree with maximum variable Randić index Rvγ, which is(14)21+γ2+γ+n−32+γ.



---

*Source: 3976274-2020-07-20.xml*