
The aim of this work is to obtain new inequalities for the variable symmetric division deg index SDDα(G)=∑uv∈E(G)(dαu/dαv+dαv/dαu), and to characterize graphs extremal with respect to them. Here, by uv we mean the edge of a graph G joining the vertices u and v, and du denotes the degree of u, and α∈R. Some of these inequalities generalize and improve previous results for the symmetric division deg index. In addition, we computationally apply the SDDα(G) index on random graphs and we demonstrate that the ratio ⟨SDDα(G)⟩/n (n is the order of the graph) depends only on the average degree ⟨d⟩.
Citation: J. A. Méndez-Bermúdez, José M. Rodríguez, José L. Sánchez, José M. Sigarreta. Analytical and computational properties of the variable symmetric division deg index[J]. Mathematical Biosciences and Engineering, 2022, 19(9): 8908-8922. doi: 10.3934/mbe.2022413
[1] | Edil D. Molina, Paul Bosch, José M. Sigarreta, Eva Tourís . On the variable inverse sum deg index. Mathematical Biosciences and Engineering, 2023, 20(5): 8800-8813. doi: 10.3934/mbe.2023387 |
[2] | Wanlin Zhu, Minglei Fang, Xianya Geng . Enumeration of the Gutman and Schultz indices in the random polygonal chains. Mathematical Biosciences and Engineering, 2022, 19(11): 10826-10845. doi: 10.3934/mbe.2022506 |
[3] | Xinmei Liu, Xinfeng Liang, Xianya Geng . Expected Value of Multiplicative Degree-Kirchhoff Index in Random Polygonal Chains. Mathematical Biosciences and Engineering, 2023, 20(1): 707-719. doi: 10.3934/mbe.2023032 |
[4] | Saylé C. Sigarreta, Saylí M. Sigarreta, Hugo Cruz-Suárez . On degree–based topological indices of random polyomino chains. Mathematical Biosciences and Engineering, 2022, 19(9): 8760-8773. doi: 10.3934/mbe.2022406 |
[5] | Qi Wang, Lifang Huang, Kunwen Wen, Jianshe Yu . The mean and noise of stochastic gene transcription with cell division. Mathematical Biosciences and Engineering, 2018, 15(5): 1255-1270. doi: 10.3934/mbe.2018058 |
[6] | V. R. Kulli, J. A. Méndez-Bermúdez, José M. Rodríguez, José M. Sigarreta . Revan Sombor indices: Analytical and statistical study. Mathematical Biosciences and Engineering, 2023, 20(2): 1801-1819. doi: 10.3934/mbe.2023082 |
[7] | Ricai Luo, Khadija Dawood, Muhammad Kamran Jamil, Muhammad Azeem . Some new results on the face index of certain polycyclic chemical networks. Mathematical Biosciences and Engineering, 2023, 20(5): 8031-8048. doi: 10.3934/mbe.2023348 |
[8] | Xiujun Zhang, H. G. Govardhana Reddy, Arcot Usha, M. C. Shanmukha, Mohammad Reza Farahani, Mehdi Alaeiyan . A study on anti-malaria drugs using degree-based topological indices through QSPR analysis. Mathematical Biosciences and Engineering, 2023, 20(2): 3594-3609. doi: 10.3934/mbe.2023167 |
[9] | Mert Sinan Oz, Roberto Cruz, Juan Rada . Computation method of the Hosoya index of primitive coronoid systems. Mathematical Biosciences and Engineering, 2022, 19(10): 9842-9852. doi: 10.3934/mbe.2022458 |
[10] | Peng Gu, Dongrong Yang, Jin Zhu, Minhao Zhang, Xiaoliang He . Bioinformatics analysis identified hub genes in prostate cancer tumorigenesis and metastasis. Mathematical Biosciences and Engineering, 2021, 18(4): 3180-3196. doi: 10.3934/mbe.2021158 |
The aim of this work is to obtain new inequalities for the variable symmetric division deg index SDDα(G)=∑uv∈E(G)(dαu/dαv+dαv/dαu), and to characterize graphs extremal with respect to them. Here, by uv we mean the edge of a graph G joining the vertices u and v, and du denotes the degree of u, and α∈R. Some of these inequalities generalize and improve previous results for the symmetric division deg index. In addition, we computationally apply the SDDα(G) index on random graphs and we demonstrate that the ratio ⟨SDDα(G)⟩/n (n is the order of the graph) depends only on the average degree ⟨d⟩.
By a graph G=(V(G),E(G)), with V(G) and E(G) the set of vertices and edges of G respectively, we mean an undirected simple graph without isolated vertices (i.e., each vertex has at least a neighbor).
Given a graph G, representing a chemical structure,
X(G)=∑uv∈E(G)F(du,dv) |
is said a topological descriptor and, if also it correlates with a molecular property, it is called a topological index. Above, by uv we mean the edge of a graph G joining the vertices u and v, du denotes the degree of u, and F is an appropriate chosen function. Remarkably, topological indices capture physical properties of a chemical compound in a single number.
A great number of topological indices have been defined and studied over more than four decades. Among them, probably the most popular topological indices are the Randić and the Zagreb indices. The first and second Zagreb indices, denoted by M1 and M2, respectively, were defined by Gutman and Trinajstić (see [1]) in 1972 by
M1(G)=∑u∈V(G)d2u,M2(G)=∑uv∈E(G)dudv. |
For more details of the applications and mathematical properties of Zagreb indices see [2,3,4], and the references therein. Zagreb indices have many connections with other topological indices, see e.g., [5,6].
The concept of variable molecular descriptors was proposed as a way of characterizing heteroatoms (see [7,8]), but also to assess structural differences in alkylcycloalkanes [9]. The idea behind the variable molecular descriptors is that the variables are determined during the regression in order to minimize the error of estimate for a particular chemical property (see, e.g., [10]).
In this line of ideas, the variable versions of the first and second Zagreb indices were introduced as [10,11,12]
Mα1(G)=∑u∈V(G)dαu,Mα2(G)=∑uv∈E(G)(dudv)α, |
with α∈R. Evidently, M21 and M12 are the first and second Zagreb indices, respectively. In addition, the first and second variable Zagreb indices include several known indices. As examples we note that M−1/22 is the Randić index, M31 is the forgotten index F, M−11 is the inverse index ID, and M−12 is the modified Zagreb index.
In 2011, Vukičević proposed the variable symmetric division deg index [13]
SDDα(G)=∑uv∈E(G)(dαudαv+dαvdαu). | (1.1) |
Note that SDD−α(G)=SDDα(G) and so, it suffices to consider positive values of α. The symmetric division deg index is the best predictor of total surface area for polychlorobiphenyls [14].
In this work we perform studies of the variable symmetric division deg index from analytical and computational viewpoints. We obtain new inequalities for the variable symmetric division deg index SDDα(G) and we characterize graphs extremal with respect to them. Some of these inequalities generalize and improve previous results for the symmetric division deg index. In addition, we computationally apply the SDDα(G) index on random graphs and we demonstrate that the ratio ⟨SDDα(G)⟩/n (n denotes the order of the graph) depends only on the average degree ⟨d⟩.
One of our main results is Theorem 8, which provides upper and lower bounds of SDDα(G) in terms of the number of edges, the maximum and the minimum degree of G.
Let us start by proving a monotonicity property of these indices.
Theorem 1. Let G be a graph and 0<α<β.Then
SDDα(G)≤SDDβ(G), |
and the equality in the bound is attained if and only if each connected component of G is a regular graph.
Proof. Let us consider x≥1. Thus, xα≥x−β and
xβ−α−1≥0,xα(xβ−α−1)≥x−β(xβ−α−1),xβ−xα≥x−α−x−β,xβ+x−β≥xα+x−α, |
for every x≥1. Since u(x)=xα+x−α satisfies u(1/x)=u(x) for every x>0, we have xβ+x−β≥xα+x−α for every x>0. Note that we obtain the equality if and only if x=1.
Thus, we have
SDDβ(G)=∑uv∈E(G)(dβudβv+dβvdβu)≥∑uv∈E(G)(dαudαv+dαvdαu)=SDDα(G). |
The previous argument gives that we have the equality in the bound if and only if du/dv=1 for every uv∈E(G), i.e., each connected component of G is a regular graph.
Our next results in this section provide bounds of SDDα(G) involving the maximum and minimum degree of the graph G. Since scientists often estimate average degree of large networks, we present in the next section results involving the average degree.
Our next theorem relates the SDDα and the variable Zagreb indices.
Theorem 2. If G is a graph with minimum degree δ and maximum degree Δ, and α>0, then
2δ2αM−α2(G)≤SDDα(G)≤2Δ2αM−α2(G),Δ−2αM2α+11(G)≤SDDα(G)≤δ−2αM2α+11(G), |
and we have the equality in each bound if and only if G is regular.
Proof. First of all recall that for every function f the following equality
∑uv∈E(G)(f(du)+f(dv))=∑u∈V(G)duf(du) |
holds. In particular,
∑uv∈E(G)(d2αu+d2αv)=∑u∈V(G)d2α+1u=M2a+11(G). |
Since
SDDα(G)=∑uv∈E(G)(dαudαv+dαvdαu)=∑uv∈E(G)d2αu+d2αv(dudv)α. |
and α>0, we obtain
SDDα(G)=∑uv∈E(G)d2αu+d2αv(dudv)α≤2Δ2α∑uv∈E(G)(dudv)−α=2Δ2αM−α2(G), |
and
SDDα(G)=∑uv∈E(G)d2αu+d2αv(dudv)α≥2δ2α∑uv∈E(G)(dudv)−α=2δ2αM−α2(G). |
We also have
SDDα(G)=∑uv∈E(G)d2αu+d2αv(dudv)α≤δ−2α∑uv∈E(G)(d2αu+d2αv)=δ−2α∑u∈V(G)d2α+1u=δ−2αM2α+11(G), |
and
SDDα(G)=∑uv∈E(G)d2αu+d2αv(dudv)α≥Δ−2α∑uv∈E(G)(d2αu+d2αv)=Δ−2α∑u∈V(G)d2α+1u=Δ−2αM2α+11(G). |
If G is a regular graph, then each lower bound and its corresponding upper bound are the same, and both are equal to SDDα(G).
Assume now that the equality in either the first or second bound holds. The previous argument gives that we have either d2αu+d2αv=2Δ2α for any uv∈E(G) or d2αu+d2αv=2δ2α for any uv∈E(G). Since α>0, we have δ2α≤d2αu,d2αv≤Δ2α, and we conclude that du=dv=Δ for any uv∈E(G), or du=dv=δ for any uv∈E(G). Hence, G is a regular graph.
Finally, assume that the equality in either the third or fourth bound holds. The previous argument gives that we have either (dudv)α=δ2α for any uv∈E(G) or (dudv)α=Δ2α for any uv∈E(G). Since α>0, we have δα≤dαu,dαv≤Δα, and we conclude that du=dv=δ for any uv∈E(G), or du=dv=Δ for every uv∈E(G). Therefore, G is a regular graph.
We will need the following technical result.
Lemma 3. Let 0<a<A. Then
a≤x2+y2x+y≤A |
for every a≤x,y≤A.The lower bound is attained if and only if x=y=a.The upper bound is attained if and only if x=y=A.
Proof. If a≤x,y≤A, then ax+ay≤x2+y2≤Ax+Ay, and the statement holds.
A large kind of topological indices, named Adriatic indices, was introduced in [14,15]. Twenty of them were selected as significant predictors of chemical properties. One of them, the inverse sum indeg index, defined by
ISI(G)=∑uv∈E(G)dudvdu+dv=∑uv∈E(G)11du+1dv. |
appears in [14,15] as a good predictor of total surface area of octane isomers.
Next, we relate SDDα(G) with the variable inverse sum deg index defined, for each a∈R, as
ISDa(G)=∑uv∈E(G)1dau+dav. |
Note that ISD−1 is the inverse sum indeg index ISI.
Theorem 4. If G is a graph with m edges and minimum degree δ, and α>0, then
SDDα(G)≥δαm2ISD−α(G), |
and the equality in the bound holds if and only if G is regular.
Proof. Lemma 3 gives
δα≤x2α+y2αxα+yα≤Δα,1x2α+y2α≤δ−αxα+yα,1d2αu+d2αv≤δ−αdαu+dαv, |
for every δ≤x,y≤Δ. This last inequality and Cauchy-Schwarz inequality give
m2=(∑uv∈E(G)1)2=(∑uv∈E(G)(d2αu+d2αvdαudαv)1/2(dαudαvd2αu+d2αv)1/2)2≤∑uv∈E(G)d2αu+d2αvdαudαv∑uv∈E(G)dαudαvd2αu+d2αv≤δ−αSDDα(G)∑uv∈E(G)dαudαvdαu+dαv=δ−αSDDα(G)∑uv∈E(G)1d−αu+d−αv=δ−αSDDα(G)ISD−α(G). |
If G is a regular graph, then SDDα(G)=2m, ISD−α(G)=mδα/2 and the equality in the bound holds.
Assume now that the equality in the bound holds. Thus, by the previous argument,
1d2αu+d2αv=δ−αdαu+dαv |
for any uv∈E(G). Then Lemma 3 gives du=dv=δ for any uv∈E(G). Hence, G is a regular graph.
The modified Narumi-Katayama index is defined by
NK∗(G)=∏u∈V(G)dduu=∏uv∈E(G)dudv |
in [16], inspired in the Narumi-Katayama index [17]. Next, we present an inequality relating SDDα(G) and NK∗(G).
Theorem 5. Let G be a graph with m edges and minimum degree δ, and α>0.Then
SDDα(G)≥2δ2αmNK∗(G)−α/m, |
and the equality in the bound holds if and only if G is a regular graph.
Proof. Since the geometric mean is at most the arithmetic mean, we have
1mSDDα(G)=1m∑uv∈E(G)(dαudαv+dαvdαu)=1m∑uv∈E(G)d2αu+d2αv(dudv)α≥2δ2α1m∑uv∈E(G)1(dudv)α≥2δ2α(∏uv∈E(G)1(dudv)α)1/m=2δ2αNK∗(G)−α/m. |
If G is a regular graph, then
2δ2αmNK∗(G)−α/m=2δ2αm(δ2m)−α/m=2m=SDDα(G). |
Finally, assume that the equality in the bound holds. The previous argument gives that d2αu+d2αv=2δ2α for any uv∈E(G). Since α>0, we obtain δ2α≤d2αu,d2αv, and we have du=dv=δ for any uv∈E(G). Hence, G is regular.
Next, we obtain additional bounds of SDDα.
Theorem 6. Let G be a graph with m edges, minimum degree δ and maximum degree δ+1, α>0 and let A be the number of edges uv∈E(G) with du≠dv.Then A is an even integer and
SDDα(G)=2m+A((δ+1)αδα+δα(δ+1)α−2). |
Proof. Let F={uv∈E(G):du≠dv}, then A is the cardinality of the set F. Since the maximum degree of G is δ+1 and its minimum degree is δ, if uv∈F, then du=δ and dv=δ+1 or viceversa, and therefore
dαudαv+dαvdαu=(δ+1)αδα+δα(δ+1)α. |
If uv∈Fc=E(G)∖F, then du=dv=δ or du=dv=δ+1, and therefore
dαudαv+dαvdαu=2. |
Since there are exactly A edges in F and m−A edges in Fc, we have
SDDα(G)=∑uv∈E(G)(dαudαv+dαvdαu)=∑uv∈Fc(dαudαv+dαvdαu)+∑uv∈F(dαudαv+dαvdαu)=∑uv∈Fc2+∑uv∈F((δ+1)αδα+δα(δ+1)α)=2m−2A+A((δ+1)αδα+δα(δ+1)α). |
This gives the equality.
Seeking for a contradiction assume that A is an odd integer.
Let Γ1 be a subgraph of G obtained as follows: Γ1 is induced by the n1 vertices with degree δ in V(G); denote by m1 the number of edges of Γ1. Handshaking Lemma implies n1δ−A=2m1. Since A is an odd integer, δ is also an odd integer. Thus, δ+1 is even.
Let Γ2 be the subgraph of G induced by the n2 vertices with degree δ+1 in V(G), and denote by m2 the number of edges of Γ2. Handshaking Lemma implies n2(δ+1)−A=2m2, a contradiction, since A is odd and δ+1 is even.
Thus, we conclude that A is an even integer.
We will need the following result in the proof of Theorem 8 below.
Lemma 7. Given α>0, consider the function u:(0,∞)→(0,∞) defined as u(t)=tα+t−α.Then u strictly decreases on (0,1], u strictly increases on [1,∞) and u(t)≥u(1)=2.
Proof. We have
u′(t)=αtα−1−αt−α−1=αt−α−1(t2α−1). |
Since α>0, we have u′<0 on (0,1) and u′>0 on (1,∞). This gives the result. The following figure shows the function u(t) for some values of α.
Theorem 6 gives the precise value of SDDα when Δ=δ+1. Theorem 8 below provides a lower bound when Δ>δ+1.
Theorem 8. Let G be a graph with m edges, minimum degree δ and maximum degree Δ>δ+1. Denote by A0,A1,A2, the cardinality of the subsets of edges F0={uv∈E(G):du=δ,dv=Δ}, F1={uv∈E(G):du=δ,δ<dv<Δ}, F2={uv∈E(G):du=Δ,δ<dv<Δ}, respectively. If α>0, then
SDDα(G)≤(m−A1−A2)(Δαδα+δαΔα)+A1((Δ−1)αδα+δα(Δ−1)α)+A2(Δα(δ+1)α+(δ+1)αΔα),SDDα(G)≥2m+A0(Δαδα+δαΔα−2)+A1((δ+1)αδα+δα(δ+1)α−2)+A2(Δα(Δ−1)α+(Δ−1)αΔα−2). |
Proof. Lemma 7 gives that the function
dαvδα+δαdαv=u(dvδ) |
is increasing in dv∈[δ+1,Δ−1] and so,
(δ+1)αδα+δα(δ+1)α≤dαvδα+δαdαv≤(Δ−1)αδα+δα(Δ−1)α, |
for every uv∈F1.
In a similar way, Lemma 7 gives that the function
Δαdαv+dαvΔα=u(dvΔ) |
is decreasing in dv∈[δ+1,Δ−1] and so,
Δα(Δ−1)α+(Δ−1)αΔα≤Δαdαv+dαvΔα≤Δα(δ+1)α+(δ+1)αΔα, |
for every uv∈F2.
Also,
2≤dαudαv+dαvdαu≤Δαδα+δαΔα |
for any uv∈E(G).
We obtain
SDDα(G)=∑uv∈E(G)∖(F0∪F1∪F2)(dαudαv+dαvdαu)+∑uv∈F0(dαudαv+dαvdαu)+∑uv∈F1(dαudαv+dαvdαu)+∑uv∈F2(dαudαv+dαvdαu)≥∑uv∈E(G)∖(F0∪F1∪F2)2+∑uv∈F0(Δαδα+δαΔα)+∑uv∈F1(dαvδα+δαdαv)+∑uv∈F2(Δαdαv+dαvΔα). |
Hence,
SDDα(G)≥2m−2A0−2A1−2A2+A0(Δαδα+δαΔα)+A1((δ+1)αδα+δα(δ+1)α)+A2(Δα(Δ−1)α+(Δ−1)αΔα). |
We also have
SDDα(G)=∑uv∈E(G)∖(F1∪F2)(dαudαv+dαvdαu)+∑uv∈F1(dαudαv+dαvdαu)+∑uv∈F2(dαudαv+dαvdαu)≤(m−A1−A2)(Δαδα+δαΔα)+A1((Δ−1)αδα+δα(Δ−1)α)+A2(Δα(δ+1)α+(δ+1)αΔα). |
Here we deal with two classes of random graphs G: Erdös-Rényi (ER) graphs G(n,p) and bipartite random (BR) graphs G(n1,n2,p). ER graphs are formed by n vertices connected independently with probability p∈[0,1]. While BR graphs are composed by two disjoint sets, sets 1 and 2, with n1 and n2 vertices each such that there are no adjacent vertices within the same set, being n=n1+n2 the total number of vertices in the bipartite graph. The vertices of the two sets are connected randomly with probability p∈[0,1]. Another work in this spirit is [18].
We stress that the computational study of the variable symmetric division deg index we perform below is justified by the random nature of the graph models we want to explore. Since a given parameter set (n,p) [(n1,n2,p)] represents an infinite-size ensemble of ER graphs [BR graphs], the computation of SDDα(G) on a single graph is irrelevant. In contrast, the computation of ⟨SDDα(G)⟩ (where ⟨⋅⟩ indicates ensemble average) over a large number of random graphs, all characterized by the same parameter set (n,p) [(n1,n2,p)], may provide useful average information about the full ensemble. This computational approach, well known in random matrix theory studies, is not widespread in studies involving topological indices, mainly because topological indices are not commonly applied to random graphs; for very recent exceptions see [19,20,21,22].
From the definition of the variable symmetric division deg index, see Eq (1.1), we have that:
(i) For α=0, ⟨SDD0(G)⟩ gives twice the average number of edges of the ER graph. That is,
⟨SDD0(G)⟩=⟨∑uv∈E(G)(d0ud0v+d0vd0u)⟩=⟨∑uv∈E(G)(1+1)⟩=⟨2|E(G)|⟩=n(n−1)p. | (3.1) |
(ii) When np≫1, we can approximate du≈dv≈⟨d⟩, then
⟨SDDα(G)⟩≈⟨∑uv∈E(G)(1α+1α)⟩=⟨∑uv∈E(G)2⟩=⟨2|E(G)|⟩=n(n−1)p. | (3.2) |
(iii) By recognizing that the average degree of the ER graph model reads as
⟨d⟩=(n−1)p, | (3.3) |
we can rewrite Eq (3.2) as
⟨SDDα(G)⟩n≈⟨d⟩. | (3.4) |
We stress that Eq (3.4) is expected to be valid for np≫1.
In Figure 2(a) we plot ⟨SDDα(G)⟩ as a function of the probability p of ER graphs of size n=500. All averages in Figure 2 are computed over ensembles of 107/n random graphs. In Figure 2(a) we show curves for α∈[0,4]. The dashed-magenta curve corresponds to the case α=0, which coincides with Eq (3.1). Moreover, we observe that
⟨SDDα≤0.5(G)⟩≈⟨SDD0(G)⟩=n(n−1)p. |
However, once α>0.5, the curves ⟨SDDα(G)⟩ versus p deviate from Eq (3.1), at intermediate values of p, in the form of a bump which is enhanced the larger the value of α is. Also, in Figure 2(a) we can clearly see that Eq (3.2) is satisfied when np≫1, as expected.
Now, in Figure 2(b) we present ⟨SDDα(G)⟩ as a function of the probability p of ER graphs of three different sizes. It is clear from this figure that the blocks of curves, characterized by the different graph sizes (and shown in different colors), display similar curves but displaced on both axes. Moreover, the fact that these blocks of curves, plotted in semi-log scale, are shifted the same amount on both x− and y−axis when doubling n make us anticipate the scaling of ⟨SDDα(G)⟩. We stress that other average variable degree-based indices on ER random graphs (normalized to the graph size) have been shown to scale with the average degree [22]. Indeed, this statement is encoded in Eq (3.4), that we derived for np≫1 but should serve as the global scaling equation for ⟨SDDα(G)⟩.
Therefore, in Figure 2(c) we show ⟨SDDα(G)⟩/n as a function of the average degree ⟨d⟩ where the same curves of Figure 2(b) have been used. There we verify the global scaling of ⟨SDDα(G)⟩, as anticipated in Eq (3.4), by noticing that the blocks of curves (painted in different colors) for different graph sizes fall on top of each other.
Also, from Figure 2(a)–(c) we observe that the inequality of Theorem 1 is extended to the average variable symmetric division deg index on random graphs:
⟨SDDα(G)⟩≤⟨SDDβ(G)⟩,0<α<β; | (3.5) |
see e.g., the blue arrow in Figure 2(a) which indicates increasing α. Here, the equality is attained if and only if p=1. However, we have observed that ⟨SDDα(G)⟩≈⟨SDDβ(G)⟩ already for ⟨d⟩≥10.
In Figure 2(d), (e) we present curves of the ⟨SDDα(G)⟩ as a function of the probability p of BR graphs. For simplicity we show results for BR graphs composed by sets of equal sizes n1=n2. In Figure 2(d) we consider the case of n1=n2=500 while in (e) we report n1=n2={125,250,500}. In both figures we show curves for α∈[0,4] in steps of 0.5.
Since edges in a bipartite graph join vertices of different sets, and we are labeling here the sets as sets 1 and 2, we replace du by d1 and dv by d2 in the expression for the SDDα(G) index below. Thus,
(i) For α=0, ⟨SDD0(G)⟩ gives twice the average number of edges of the BG graph. That is,
⟨SDD0(G)⟩=⟨∑E(G)(d01d02+d02d01)⟩=⟨∑E(G)(1+1)⟩=⟨2|E(G)|⟩=2n1n2p. | (3.6) |
(ii) When both n1p≫1 and n2p≫1, we can approximate d1≈⟨d1⟩ and d2≈⟨d2⟩, then
⟨SDDα(G)⟩≈⟨∑E(G)(⟨d1⟩α⟨d2⟩α+⟨d2⟩α⟨d1⟩α)⟩=⟨|E(G)|(⟨d1⟩α⟨d2⟩α+⟨d2⟩α⟨d1⟩α)⟩. | (3.7) |
(iii) In the case we consider in Figure 2(d)–(f), where n1=n2=n/2, so that ⟨d1⟩=⟨d2⟩=⟨d⟩, Equation (3.7) reduces to
⟨SDDα(G)⟩≈⟨2|E(G)|⟩=2n1n2p=n22p. | (3.8) |
(iv) By recognizing that ⟨d⟩=np/2 we can rewrite Eq (3.8) as
⟨SDDα(G)⟩n≈⟨d⟩. | (3.9) |
We stress that Eq (3.9) is expected to be valid for np≫1. We also note that Eq (3.9) has exactly the same form as Eq (3.4).
From Figure 2(d), (e) we note that
⟨SDDα≤0.5(G)⟩≈⟨SDD0(G)⟩=2n1n2p, |
see the dashed-magenta curve in Figure 2(d). But once α>0.5, the curves ⟨SDDα(G)⟩ versus p deviate from Eq (3.6), at intermediate values of p, in the form of bumps which are enhanced the larger the value of α is. These bumps make clear the validity of inequality (3.5) on BR graphs; see e.g., the blue arrow in Figure 2(d) which indicates increasing α.
Finally, following the scaling analysis made in the previous subsection for ER graphs, in Figure 2(f) we plot the ⟨SDDα(G)⟩/n as a function of the average degree ⟨d⟩ where the same data sets of Figure 2(e) have been used. Thus we verify that ⟨SDDα(G)⟩/n scales with ⟨d⟩, as anticipated in Eq (3.9); that is, the blocks of curves (painted in different colors) for different graph sizes coincide.
In this paper we have performed analytical and computational studies of the variable symmetric division deg index SDDα(G). First, we provided a monotonicity property and obtained new inequalities connecting SDDα(G) with other well–known topological indices such as the variable inverse sum deg index, as well as the the modified Narumi-Katayama index. Then, we apply the index SDDα(G) on two ensembles of random graphs: Erd\H{o}s-Rényi graphs and bipartite random graphs. Thus, we computationally showed, for both random graph models, that the ratio ⟨SDDα(G)⟩/n is a function of the average degree ⟨d⟩ only (n being the order of the graph). We note that this last result, also observed for other variable topological indices [22], is valid for random bipartite graphs only when they are formed by sets of the same size.
Since many important topological indices can be written as
X(G)=∑uv∈E(G)F(du,dv), |
an open problem is to extend the results of this paper to other indices of this kind.
J. A. M.-B. has been supported by CONACyT (Grant No. CB-2016-286633-F). J. M. R. and J. M. S. have been supported by a grant from Agencia Estatal de Investigación (PID2019-106433GBI00/AEI/10.13039/501100011033), Spain. J. M. R. has been supported by the Madrid Government (Comunidad de Madrid-Spain) under the Multiannual Agreement with UC3M in the line of Excellence of University Professors (EPUC3M23), and in the context of the V PRICIT (Regional Programme of Research and Technological Innovation).
The authors declare there is no conflict of interest.
[1] |
I. Gutman, N. Trinajstić, Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17 (1972), 535–538. https://doi.org/10.1016/0009-2614(72)85099-1 doi: 10.1016/0009-2614(72)85099-1
![]() |
[2] |
I. Gutman, Degree–based topological indices, Croat. Chem. Acta, 86 (2013), 351–361. https://doi.org/10.5562/cca2294 doi: 10.5562/cca2294
![]() |
[3] | I. Gutman, K. C. Das, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem., 50 (2004), 83–92. |
[4] | I. Gutman, T. Réti, Zagreb group indices and beyond, Int. J. Chem. Model., 6 (2014), 191–200. |
[5] | K. C. Das, A. S. Cevik, I. N. Cangul, Y. Shang, On Sombor index, Symmetry, 13 (2021), 140. https://doi.org/10.3390/sym13010140 |
[6] |
H. A. Ganie, Y. Shang, On the spectral radius and energy of signless Laplacian matrix of digraphs, Heliyon, 8 (2022), e09186. https://doi.org/10.1016/j.heliyon.2022.e09186 doi: 10.1016/j.heliyon.2022.e09186
![]() |
[7] |
M. Randić, Novel graph theoretical approach to heteroatoms in QSAR, Chemometrics Intel. Lab. Syst., 10 (1991), 213–227. https://doi.org/10.1016/S0167-9260(06)80016-7 doi: 10.1016/S0167-9260(06)80016-7
![]() |
[8] |
M. Randić, On computation of optimal parameters for multivariate analysis of structure-property relationship, J. Chem. Inf. Comput. Sci., 31 (1991), 970–980. https://doi.org/10.1021/ci00002a002 doi: 10.1021/ci00002a002
![]() |
[9] |
M. Randić, D. Plavšić, N. Lerš, Variable connectivity index for cycle-containing structures, J. Chem. Inf. Comput. Sci., 41 (2001), 657–662. https://doi.org/10.1021/ci000118z doi: 10.1021/ci000118z
![]() |
[10] | A. Miličević, S. Nikolić, On variable Zagreb indices, Croat. Chem. Acta, 77 (2004), 97–101. |
[11] |
X. Li, J. Zheng, A unified approach to the extremal trees for different indices, MATCH Commun. Math. Comput. Chem., 54 (2005), 195–208. https://doi.org/10.1093/english/54.210.195 doi: 10.1093/english/54.210.195
![]() |
[12] | X. Li, H. Zhao, Trees with the first smallest and largest generalized topological indices, MATCH Commun. Math. Comput. Chem., 50 (2004), 57–62. |
[13] |
D. Vukičević, Bond additive modeling 5. Mathematical properties of the variable sum exdeg index, Croat. Chem. Acta, 84 (2011), 93–101. https://doi.org/10.5562/cca1667 doi: 10.5562/cca1667
![]() |
[14] | D. Vukičević, M. Gašperov, Bond additive modeling 1. Adriatic indices, Croat. Chem. Acta, 83 (2010), 243–260. |
[15] |
D. Vukičević, Bond additive modeling 2. Mathematical properties of max-min rodeg index, Croat. Chem. Acta, 83 (2010), 261–273. https://doi.org/10.1093/biolreprod/83.s1.261 doi: 10.1093/biolreprod/83.s1.261
![]() |
[16] | M. Ghorbani, M. Songhori, I. Gutman, Modified Narumi-Katayama index, Kragujevac J. Sci., 34 (2012), 57–64. |
[17] |
H. Narumi, M. Katayama, Simple topological index. A newly devised index characterizing the topological nature of structural isomers of saturated hydrocarbons, Mem. Fac. Engin. Hokkaido Univ., 16 (1984), 209–214. https://doi.org/10.1016/0020-1383(84)90191-8 doi: 10.1016/0020-1383(84)90191-8
![]() |
[18] |
Y. Shang, Sombor index and degree-related properties of simplicial networks, Appl. Math. Comput., 419 (2022), 126881. https://doi.org/10.1016/j.amc.2021.126881 doi: 10.1016/j.amc.2021.126881
![]() |
[19] |
C. T. Martínez-Martínez, J. A. Mendez-Bermudez, J. M. Rodríguez, J. M. Sigarreta, Computational and analytical studies of the Randic index in Erdös-Rényi models, Appl. Math. Comput., 377 (2020), 125137. https://doi.org/10.1016/j.amc.2020.125137 doi: 10.1016/j.amc.2020.125137
![]() |
[20] | C. T. Martínez-Martínez, J. A. Mendez-Bermudez, J. M. Rodríguez, J. M. Sigarreta, Computational and analytical studies of the harmonic index in Erdös–Rényi models, MATCH Commun. Math. Comput. Chem., 85 (2021), 395–426. |
[21] |
R. Aguilar-Sanchez, J. A. Mendez-Bermudez, J. M. Rodríguez, J. M. Sigarreta-Almira, Analytical and statistical studies of Rodriguez-Velazquez indices, J. Math. Chem., 59 (2021), 1246–1259. https://doi.org/10.1007/s10910-021-01239-1 doi: 10.1007/s10910-021-01239-1
![]() |
[22] |
R. Aguilar-Sanchez, I. F. Herrera-Gonzalez, J. A. Mendez-Bermudez, J. M. Sigarreta, Computational properties of general indices on random networks, Symmetry, 12 (2020), 1341. https://doi.org/10.3390/sym12081341 doi: 10.3390/sym12081341
![]() |