Loading [MathJax]/jax/output/SVG/jax.js
Research article

On symmetric division deg index of trees with given parameters

  • Received: 07 January 2021 Accepted: 13 April 2021 Published: 15 April 2021
  • MSC : 05C07, 05C35, 92E10

  • Recently, the symmetric division deg (SDD) index is proven to be a potentially useful molecular descriptor in QSAR and QSPR (quantitative structure-activity and structure-property relationships) studies. And its predictive capability is better than that of some popular topological indices, such as the famous geometric-arithmetic index and the second Zagreb index. In this work, the maximum SDD indices of trees with given matching number or domination number or independence number or number of pendant vertices or segments or diameter or radius are presented. Furthermore, the corresponding extremal trees are identified.

    Citation: Jianwei Du, Xiaoling Sun. On symmetric division deg index of trees with given parameters[J]. AIMS Mathematics, 2021, 6(6): 6528-6541. doi: 10.3934/math.2021384

    Related Papers:

    [1] Xiaoling Sun, Yubin Gao, Jianwei Du . On symmetric division deg index of unicyclic graphs and bicyclic graphs with given matching number. AIMS Mathematics, 2021, 6(8): 9020-9035. doi: 10.3934/math.2021523
    [2] Zhibin Du, Ayu Ameliatul Shahilah Ahmad Jamri, Roslan Hasni, Doost Ali Mojdeh . Maximal first Zagreb index of trees with given Roman domination number. AIMS Mathematics, 2022, 7(7): 11801-11812. doi: 10.3934/math.2022658
    [3] Hicham Saber, Zahid Raza, Abdulaziz M. Alanazi, Adel A. Attiya, Akbar Ali . On trees with a given number of segments and their maximum general Z-type index. AIMS Mathematics, 2025, 10(1): 195-207. doi: 10.3934/math.2025010
    [4] Shahid Zaman, Fouad A. Abolaban, Ali Ahmad, Muhammad Ahsan Asim . Maximum H-index of bipartite network with some given parameters. AIMS Mathematics, 2021, 6(5): 5165-5175. doi: 10.3934/math.2021306
    [5] Akbar Ali, Sneha Sekar, Selvaraj Balachandran, Suresh Elumalai, Abdulaziz M. Alanazi, Taher S. Hassan, Yilun Shang . Graphical edge-weight-function indices of trees. AIMS Mathematics, 2024, 9(11): 32552-32570. doi: 10.3934/math.20241559
    [6] Chang Liu, Jianping Li . Sharp bounds on the zeroth-order general Randić index of trees in terms of domination number. AIMS Mathematics, 2022, 7(2): 2529-2542. doi: 10.3934/math.2022142
    [7] Akbar Ali, Sadia Noureen, Akhlaq A. Bhatti, Abeer M. Albalahi . On optimal molecular trees with respect to Sombor indices. AIMS Mathematics, 2023, 8(3): 5369-5390. doi: 10.3934/math.2023270
    [8] Fei Yu, Hifza Iqbal, Saira Munir, Jia Bao Liu . M-polynomial and topological indices of some transformed networks. AIMS Mathematics, 2021, 6(12): 13887-13906. doi: 10.3934/math.2021804
    [9] Zhen Lin, Ting Zhou, Xiaojing Wang, Lianying Miao . The general Albertson irregularity index of graphs. AIMS Mathematics, 2022, 7(1): 25-38. doi: 10.3934/math.2022002
    [10] Abel Cabrera-Martínez, Andrea Conchado Peiró, Juan Manuel Rueda-Vázquez . Further results on the total Italian domination number of trees. AIMS Mathematics, 2023, 8(5): 10654-10664. doi: 10.3934/math.2023540
  • Recently, the symmetric division deg (SDD) index is proven to be a potentially useful molecular descriptor in QSAR and QSPR (quantitative structure-activity and structure-property relationships) studies. And its predictive capability is better than that of some popular topological indices, such as the famous geometric-arithmetic index and the second Zagreb index. In this work, the maximum SDD indices of trees with given matching number or domination number or independence number or number of pendant vertices or segments or diameter or radius are presented. Furthermore, the corresponding extremal trees are identified.



    Topological molecular descriptors are mathematical invariants reflecting some biological and physico-chemical properties of organic compounds on the chemical graph, and they play a substantial role in materials science, chemistry and pharmacology, etc. (see [1,2,3]). Symmetric division deg (SDD for short) index is one of the 148 discrete Adriatic indices that showed good predictive properties on the testing sets provided by International Academy of Mathematical Chemistry (IAMC) [4]. This graph descriptor has a good correlation with the total surface area of polychlorobiphenyls [4] and its extremal graphs which have a particularly elegant and simple structure are obtained with the help of MathChem [5]. SDD index is defined as

    SDD(G)=uvE(G)(min{dG(u),dG(v)}max{dG(u),dG(v)}+max{dG(u),dG(v)}min{dG(u),dG(v)})=uvE(G)(dG(u)dG(v)+dG(v)dG(u)),

    where dG(u) denotes the degree of vertex u in G. Recently, Furtula et al. [6] found that SDD index is an applicable and viable topological index, whose predictive capability is better than that of some popular topological indices. Gupta et al. [7] determined some upper and lower bounds of SDD index on some classes of graphs and characterized the corresponding extremal graphs. For other recent mathematical investigations, the readers can refer [8,9,10,11,12,13].

    We only deal with the simple connected graphs in this work. Let G=(V(G), E(G)) be the graph having vertex set V(G) and edge set E(G). Let us denote the maxmium degree of G by Δ(G). We use dG(x,y) to denote the distance between two vertices x and y in G. Denoted by Guv the graph arising from G by deleting the edge uvE(G). The subetaaph of G obtained by deleting the vertex x (xV(G)) and its incident edges is denoted by Gx. Let Pn and Sn be the n-vertex path and the n-vertex star, respectively.

    A matching in G is a subset ME(G) if no two edges in M are adjacent. An independent set is a subset of vertices in which no two elements are adjacent. The matching number and the independence number of a graph G is the maximum cardinality of a matching and an independent set in G, respectively. A dominating set of a graph is a vertex set VV(G) if each vertex of V(G)V is adjacent to at least one vertex of V. The domination number of a graph G, denoted by κ(G), is the minimum cardinality among all dominating sets. The eccentricity εG(x) of a vertex xV(G) is defined as εG(x)=max{dG(x,y)|yV(G)}. The diameter and radius of a graph G is the maximum eccentricity and the minimum eccentricity over all vertices in G, respectively. A segment of a tree T (see [14]) is a path-subtree whose terminal vertices are pendent or branching vertices (the vertex with degree 3 or greater) of T. We can see [15] for other terminologies and notations.

    Denoted by TTn,m the set of trees of order n with matching number m. Thus TT2m,m are trees with a perfect matching. Let us denote the set of all pendant vertices in T by PV(T).

    Let TTn,m be the tree of order n obtained from Snm+1 by attaching one pendant edge to each of certain m1 pendant vertices of Snm+1.

    Let

    S(x,y)=yx+xy, where x,y1,

    and

    f(n,x)=(nx)(n3x2+12)+52(x1)+n1nx, where n2, x1 and xn2.

    One can easily get the following Lemmas 2.1-2.4.

    Lemma 2.1. Let ft(x)=S(x,t+1)S(x,t)=xt+1xt+1x, where x,t1. Then ft(x) is decreasing for x.

    Lemma 2.2. Let h(t)=t+1t1t+1, where t1. Then h(t) is increasing for t.

    Lemma 2.3. Let T be a tree. If dT(x,z) is maximum, where x,zV(T), then z is a pendant vertex.

    Lemma 2.4. Let TTT2m,m and yV(T). Then NT(y)PV(T)∣≤1.

    Lemma 2.5. [16] Let TTT2m,m. If x,zV(T) and dT(x,z) is maximum, then z is adjacent to a vertex of degree two.

    Theorem 2.6. Let TTT2m,m, where m1. Then

    SDD(T)f(2m,m)=m22+3m1m12

    with equality only when TTT2m,m.

    Proof. By induction on m. If m=1, TTT2,1 and SDD(T)=2=f(2,1).

    Suppose the theorem holds for all trees on fewer than 2m4 vertices with a perfect matching. Let x be a vertex satisfying dT(x,z)=max{dT(x,y),yV(T)}. Since TTT2m,m and |V(T)|=2m4, then dT(x,z)3 (notice that dT(x,z)=3 only if TP4TT4,2 holds). By Lemma 2.3, it follows that z is a pendant vertex. Let uzE(T). By lemma 2.5, dT(u)=2. Let NT(u)={v,z} (v belongs to the vertices of the path from x to u in T) and NT(v)={v1,v2,,vt,w}, where w belongs to the vertices of the path from x to v in T and v1=u (notice that if w=x, then TP4TT4,2). We discuss in two cases.

    Case 1. vwM.

    In this case, there exists wNT(w) and viNT(v) such that wwM and vviM, where i1. Assume without loss of generality that vvtM. Thus it can be seen that vt is a pendant vertex. Otherwise, there exists vertex vtNT(vt){v}. By Lemma 2.4, vt is a pendant vertex. Since TTT2m, we have vtvtM, which contradicts vvtM. By Lemma 2.5, we have dT(vi)=2, 1it1. Let NT(vi){v}={zi}, 1it1, where z1=z. Notice that viziM, 1it1. Set T=Tv1z1. Thus TTT2(m1),m1. By the definition of SDD index, induction hypothesis and Lemmas 2.1, 2.2, we have

    SDD(T)=SDD(T)+[S(dT(w),dT(v))S(dT(w),dT(v)1)]+S(dT(v1),dT(v))+S(dT(v1),dT(z1))+t1i=2[S(dT(vi),dT(v))S(dT(vi),dT(v)1)]+S(dT(vt),dT(v))S(dT(vt),dT(v)1)SDD(T)+[S(2,dT(v))S(2,dT(v)1)]+S(2,dT(v))+S(2,1)+t1i=2[S(2,dT(v))S(2,dT(v)1)]+S(1,dT(v))S(1,dT(v)1)f(2(m1),m1)+(t1)(12+2t+12t)+2t+1+t2+12+52+1+1t+11t=f(2(m1),m1)+t+1t1t+1+72f(2(m1),m1)+m1+1m11m+72=f(2m,m)

    since tm1. With the equalities hold only if SDD(T)=f(2(m1),m1), t=m1, dT(w)=2 and V(T)={w,w,v,vt}{v1,v2,, vt1}{z1,z2,,zt1}. It implies that TTT2(m1),m1, and TTT2m,m.

    Case 2. vwM.

    Note that (NT(v){w})PV(T)=. Otherwise, for y(NT(v){w})PV(T), y is not M-saturated, which contradicts TTT2m,m. Thus we have dT(vi)2, 1it. In view of Lemma 2.3, we can get that (NT(vi){v})PV(T), 1it. And by Lemma 2.5, we have dT(vi)=2, 1it. Let NT(vi){v}={zi}, 1it, where z1=z. Notice that viziM, 1it. Set T=Tv1z1. Thus TTT2(m1),m1. By induction hypothesis and Lemmas 2.1, 2.2, we have

    SDD(T)=SDD(T)+[S(dT(w),dT(v))S(dT(w),dT(v)1)]+ti=2[S(dT(vi),dT(v))S(dT(vi),dT(v)1)]+S(dT(v1),dT(v))+S(dT(v1),dT(z1))SDD(T)+[S(1,dT(v))S(1,dT(v)1)]+ti=2[S(2,dT(v))S(2,dT(v)1)]+S(2,dT(v))+S(2,1)f(2(m1),m1)+(1t+11t+1)+(t1)(12+2t+12t)+2t+1+t+12+52=f(2(m1),m1)+t+1t1t+1+72f(2(m1),m1)+m+1m11m+52=f(2m,m)

    since tm1. With equalities hold only if SDD(T)=f(2(m1),m1), dT(w)=1, t=m1 and V(T)={w,v}{v1,v2,,vt}{z1,z2,,zt}. It implies that t=1, w=x and TTT2,1. Therefore we have TTT4,2.

    Lemma 2.7. Let l(s,t)=32s+t1s1ts=32s+tss(s1), where s,t2 and s>t. Then l(s,t) is increasing for s and t, respectively.

    Proof. It is evident that l(s,t) is increasing for t. Furthermore, since

    ls=32t1(s1)2+ts2=32+s2(2s1)ts2(s1)2>32+s2(2s1)s(s1)2s2=321(s1)s3212>0,

    then l(s,t) is increasing for s.

    Theorem 2.8. Let TTTn,m. Then

    SDD(T)f(n,m).

    The equality holds only when TTTn,m.

    Proof. By induction on n. If n=2m, by Theorem 2.6, the result holds.

    Suppose the result holds for all T on fewer than n (n>2m) vertices. Let M be an m-matching. Denoted by Pd+1=x1x2xd+1 a path of length d, where d is the diameter of T. If d2, then TSnTTn,1 and SDD(T)=f(n,1). In what follows, we suppose d3. By Lemma 2.3, we can see that x1 is a pendant vertex. Denote NT(x2)={x3,u1,u2,,ur1} and NT(x3)={x2,x4,v1,v2,,vs2}, where r,s2 and u1=x1. It is evident that dT(ui)=1 (1ir1). We discuss in two cases.

    Case 1. x2x3M.

    Now u1=x1 is not M-saturated. Set T1=Tu1. Then T1TTn1,m. Since there exist at least m1 edges for each matching in T{x2,x3,u1,u2,,ur1}, then n(r+1)2(m1), that is rn2m+1. By induction hypothesis and Lemmas 2.1, 2.2, it follows that

    SDD(T)=SDD(T1)+S(1,r)+S(s,r)S(s,r1)+(r2)(S(1,r)S(1,r1))SDD(T1)+S(1,r)+S(2,r)S(2,r1)+(r2)(S(1,r)S(1,r1))f(n1,m)+2r321r1+1rf(n1,m)+2(n2m+1)321n2m+1n2m+1=f(n,m)2n+52m+12n1nm+n2nm1+2(n2m+1)321n2m+1n2m+1=f(n,m)32mn1nm+n2nm11n2m+1n2m+1+1<f(n,m)32m+m1(nm)(nm1)+1<f(n,m)32m+32<f(n,m).

    Case 2. x2x3M.

    Since M is an m-matching in T, now there is uiNT(x2) with x2uiM. Without loss of generality, assume that x2u1M.

    Case 2.1. r=2.

    Set T2=Tu1x2. Then T2TTn2,m1.

    Case 2.1.1. s=2.

    By induction hypothesis and Lemma 2.1, it follows that

    SDD(T)=SDD(T2)+S(d(x4),2)S(d(x4),1)+S(2,2)+S(2,1)f(n2,m1)+S(2,2)S(2,1)+2+52=f(n2,m1)+4=f(n,m)32n+2mn1nm+n3nm1+32=f(n,m)32n+2mn2m+1(nm1)(nm)+32f(n,m)32n+2m+32f(n,m)32(2m+1)+2m+32f(n,m)m<f(n,m).

    Case 2.1.2. s3.

    Without loss of generality, we suppose that d(v1)=d(v2)==d(vt)=1 and d(vt+1), d(vt+2),,d(vs2)2. If d=3, then d(x4)=1, d(v1)=d(v2)==d(vs2)=1 and this implies TTTn,2. So we assume that d4. Since there exist at least m3 M-saturated vertices in V(T){x1,x2,,x5,v1,v2,,vs2}, then |V(T)|=n|{x1,x2,,x5,v1,v2,,vs2}|+m3=s+m, that is snm.

    Case 2.1.2.1. t1.

    By induction hypothesis and Lemmas 2.1, 2.2, it follows that

    SDD(T)=SDD(T2)+S(d(x4),s)S(d(x4),s1)+S(d(v1),s)S(d(v1),s1)+s2i=2(S(d(vi),s)S(d(vi),s1))+S(2,s)+S(2,1)f(n2,m1)+(s2)(S(2,s)S(2,s1))+S(1,s)S(1,s1)+S(2,s)+S(2,1)=f(n2,m1)+s+521s+1s1f(n,m)32n+2m52n1nm+n3nm1+nm+521nm+1nm1=f(n,m)n2+mn2m(nm)(nm1)<f(n,m)n2+m<f(n,m).

    Case 2.1.2.2. t2.

    Since there are at least t1 pendant vertices which are not M-saturated, then n(t1)2m, that is tn2m+1. Set T3=Tv1. Then T3TTn1,m. By induction hypothesis and Lemmas 2.1, 2.7, it follows that

    SDD(T)=SDD(T3)+S(d(x4),s)S(d(x4),s1)+S(2,s)S(2,s1)+S(1,s)+ti=2(S(1,s)S(1,s1))+s2i=t+1(S(d(vi),s)S(d(vi),s1))f(n1,m)+(st)(S(2,s)S(2,s1))+S(1,s)+(t1)(S(1,s)S(1,s1))=f(n1,m)+t2+32(s2)+22st1s1+2sts=f(n1,m)+t2+32sts+t1s11f(n1,m)+t2+32(nm)tnm+t1nm11f(n1,m)+n2m+12+32(nm)n2m+1nm+n2mnm11=f(n,m).

    The equalities hold only if d(x4)=2, t=n2m+1, s=nm and T3TTn1,m. This implies TTTn,m.

    Case 2.2. r3.

    In this case, u2,,ur1 is not M-saturated and n(r2)2m, that is rn2m+2. Since d3, then x3x4E(T). Set T4=Tu2. Then T4TTn1,m. If m=2, then TTTn,2. If m3, By induction hypothesis and Lemmas 2.1, 2.2, it follows that

    SDD(T)=SDD(T4)+S(d(x3),r)S(d(x3),r1)+S(1,r)S(1,r1)+S(1,r)+r1i=3(S(1,r)S(1,r1))f(n1,m)+S(2,r)S(2,r1)+(r2)(S(1,r)S(1,r1))+S(1,r)=f(n1,m)+2r+1r1r132f(n1,m)+2(n2m+2)+1n2m+21n2m+132<f(n1,m)+2(n2m+2)32=f(n,m)32m+3+(m1)(1nm11nm)<f(n,m)32m+3+13<f(n,m)

    since 1nm11nm<1m11m for nm>m (n>2m).

    The proof is completed.

    Suppose G ia a bipartite graph on n vertices with matching number m and independence number β. That, as we all know, m+β=n for any bipartite graph G, see [15]. Since a tree is a bipartite graph, by Theorem 2.8, the Theorem 2.9 is immediate.

    Theorem 2.9. Suppose T is a tree on n vertices with independence number β. Then

    SDD(T)f(n,nβ).

    With equality if and only if TTTn,nβ.

    It is evident that κ(T)=1 for a tree T on n vertices if and only if TSn. It is well known that for a graph G on n vertices, κ(G)n2 [17]. Fink et al [18] determined the n-vertex graphs G with κ(G)=n2. Let TTn,κ be the n-vertex trees with domination number κ. Note that for TTTn,κ with Δ(T)=nκ, then TTTn,κ.

    Theorem 3.1. Let TTTn,κ, where n3 and κn2. Then

    SDD(T)f(n,κ).

    The equality holds only when TTTn,κ.

    Proof. If n=3, TP3TT3,1 and SDD(P3)=5=f(3,1). If n=4, TP4TT4,2 or S4TT4,1, and SDD(P4)=7=f(4,2), SDD(S4)=10=f(4,1). Now, suppose n5 and the theorem holds for any T on fewer than n vertices. We use Pd+1=x1x2xd+1 to denote a path of length d, where d is the diameter of T. If d=2, then TSn and κ(Sn)=1, the result is ture. So in what follows, we suppose that κ(T)2. Denote NT(x2)={x1,x3,u1,u2,,ur2} and NT(x3)={x2,x4,v1,v2,,vs2}, where r,s2. Set T1=T{x1}.

    Case 1. κ(T1)=κ(T).

    By the definition of SDD index, induction hypothesis and Lemma 2.1, it follows that

    SDD(T)=SDD(T1)+S(1,r)+S(r,s)S(r1,s)+(r2)(S(1,r)S(1,r1))f(n1,κ)+S(1,r)+S(r,2)S(r1,2)+(r2)(S(1,r)S(1,r1))=f(n,κ)2n+52κ+12+n2nκ1n1nκ+2r+1r1r132.

    Since κn(r2)2, that is rn2κ+2, by Lemma 2.2, it follows that

    SDD(T)f(n,κ)2n+52κ+12+n2nκ1n1nκ+2(n2κ+2)+1n2κ+21n2κ+132=f(n,κ)32κ+3+n2nκ1n1nκ+1n2κ+21n2κ+1.

    If κ=2, SDD(T)f(n,κ). The equalities hold if only s=2 and n=r+2. This implies TTTn,2. If κ3, we have

    SDD(T)<f(n,κ)32κ+3+n2nκ1n1nκ=f(n,κ)32κ+3+κ1(nκ)(nκ1).

    Since κ1(nκ)(nκ1)<1, then for κ3, SDD(T)<f(n,κ)32κ+4<f(n,κ)12<f(n,κ).

    Case 2. κ(T1)=κ(T)1.

    In this case, we have r=2, otherwise x2 belongs to each minimum dominating set and implies κ(T1)=κ(T). For s=nκ, then TTTn,κ, and the theorem holds. So in what follows, we assume that snκ1. By the case 1 above, assume that d(vi)2, i{1,2,,s2}. If x4 is a pendant vertex or a support vertex with d(x4)=2, then TTTn,κ. In other cases, without loss of generality, let d(v1)==d(vs1)=1, d(vs1+1)==d(vs1+s2)=2, where s1+s2=s2.

    Case 2.1. s12.

    Set T2=T{v1}. Then κ(T2)=κ(T). By the definition of SDD index, induction hypothesis and Lemma 2.1, it follows that

    SDD(T)=SDD(T2)+S(s,2)S(s1,2)+S(s,1)+S(s,d(x4))S(s1,d(x4))+(s11)(S(s,1)S(s1,1))+s2(S(s,2)S(s1,2))SDD(T2)+s+1s+(s11)(1+1s1s1)+(s2+2)(12+2s2s1)f(n,κ)2n+52κ+12n1nκ+n2nκ1+32s+s121+s1ss(s1)<f(n,κ)2n+52κ+12n1nκ+n2nκ1+32s+s121.

    Since snκ1, κn(s11)2 and n1nκ+n2nκ1=κ1(nκ)(nκ1)<1. Therefore

    SDD(T)<f(n,κ)2n+52κ+12+32(nκ1)+n2κ+12=f(n,κ)12<f(n,κ).

    Case 2.2. s11.

    Set T3=T{x1,x2}. By the definition of SDD index, induction hypothesis and Lemma 2.1, it follows that

    SDD(T)=SDD(T3)+S(s,d(x4))S(s1,d(x4))+S(s,d(v1))S(s1,d(v1))+S(s,2)+S(1,2)+(s3)(S(s,2)S(s1,2))SDD(T3)+1+1s1s1+(s2+2s)+52+(s2)(12+2s2s1)f(n2,κ1)+s+52+1s11sf(n,κ)32n+2κ52n1nκ+n3nκ1+s+52+1s11s.

    Since snκ1, 1s11s=1s(s1)12 and n1nκ+n3nκ1=2κn1(nκ)(nκ1)<0. Therefore

    SDD(T)<f(n,κ)32n+2κ+nκ1+12=f(n,κ)n2+κ12f(n,κ)12<f(n,κ).

    The proof is completed.

    Let TT(1)n,s and TT(2)n,p be the n-vertex trees with s segments and p pendant vertices, respectively. TT(1)n,1 is a path, TT(1)n,2 is empty and TT(1)n,n1 is a tree containing no vertex of degree 2 (see [19]). In [18], Vasilyev proved that Sn has the maximum SDD index for any tree T on n vertices, so Sn also has the maximum SDD index for TTT(1)n,n1. Furthermore, TT(2)n,2 is a path, TT(2)n,n1 is star. Thus we only consider the case of 3sn2 (3pn2, respectively) when TTT(1)n,s (TTT(2)n,p, respectively). Let

    g(n,x)=2n+x252x12+1x, where n5 and 2xn2.

    Let TTn,s be the tree of order n obtained from Pns+1 by attaching s1 pendant edge to one pendant vertex of Pns+1.

    Theorem 4.1. Let TTT(1)n,s, where n5 and 3sn2. Then

    SDD(T)g(n,s)

    with equality only when TTTn,s.

    Proof. By induction on n. If n=5, then s=3, TTT5,3 and SDD(TT5,3)=g(5,3), the result holds. Now, suppose n6 and the result holds for any T of order n1. Denoted by Pd+1=x1x2xd+1 a path of length d, where d is the diameter of T. If d=2, then TSn. Therefore d3. Set T=T{x1}.

    Case 1. d(x2)=2.

    Then TTT(1)n1,s. By induction hypothesis and Lemma 2.1, it follows that

    SDD(T)=SDD(T)+S(1,2)+S(2,d(x3)S(1,d(x3))g(n1,s)+S(2,2)=g(n,s).

    With equality only when d(x3)=2 and TTTn1,s. This implies TTTn,s.

    Case 2. d(x2)3.

    Denote NT(x2){x1,x3}={u1,u2,,ut}, where t1. Then u1,u2,,ut are pendant vertices and TTT(1)n1,s1. Since ts2, by induction hypothesis and Lemmas 2.1, 2.2, it follows that

    SDD(T)=SDD(T)+S(1,t+2)+ti=1(S(t+2,d(ui))S(t+1,d(ui)))+S(t+2,d(x3))S(t+1,d(x3))g(n1,s1)+S(1,t+2)+t(S(t+2,1)S(t+1,1))+S(t+2,2)S(t+1,2)=g(n1,s1)+2t+52+1t+21t+1g(n1,s1)+2(s2)+52+1s1s1=g(n,s).

    The equalities hold if only d(x3)=2 and TTTn1,s1. This implies TTTn,s.

    By a similar proof of Theorem 4.1, we can get Theorem 4.2.

    Theorem 4.2. Let TTT(2)n,p, where n5 and 3pn2. Then

    SDD(T)g(n,p)

    with equality if and only if TTTn,p.

    Let TT(3)n,d be the n-vertex trees with diameter d. Since TT(3)n,2Sn, so we consider the case of 3dn1 when TTT(3)n,d.

    Theorem 5.1. Let TTT(3)n,d, where 3dn1. Then

    SDD(T)g(n,nd+1)

    with equality only when TTTn,nd+1.

    Proof. By induction on n. If n=4, then d=3, TP4TT4,2 and SDD(P4)=g(4,2), the result holds. Now, suppose n5 and the theorem holds for any T on n1 vertices. We use Pd+1=x1x2xd+1 to denote a path of length d in T. Set T=T{x1}.

    Case 1. d(x2)=2.

    If the diameter of T is d, since 1ndn3, by induction hypothesis and Lemma 2.1, it follows that

    SDD(T)=SDD(T)+S(1,2)+S(2,d(x3)S(1,d(x3))g(n1,nd)+S(2,2)=g(n,nd+1)2(nd)+321nd+1+1ndg(n,nd+1)2+32+112g(n,nd+1).

    The equalities hold if only d(x3)=2, nd=1 and TTTn1,nd. But these cannot hold together, so SDD(T)<g(n,nd+1).

    If the diameter of T is d1, by induction hypothesis and Lemma 2.1, it follows that

    SDD(T)g(n1,nd+1)+S(2,2)=g(n,nd+1).

    The equality holds if only d(x3)=2 and TTTn1,nd+1. This implies TTTn,nd+1.

    Case 2. d(x2)3.

    Denote NT(x2){x1,x3}={u1,u2,,ut}, where t1 and u1,u2,,ut are pendant vertices. Then the diameter of T is d. Since tn(d+1), by induction hypothesis and Lemmas 2.1, 2.2, we have

    SDD(T)=SDD(T)+S(1,t+2)+ti=1(S(t+2,d(ui))S(t+1,d(ui)))+S(t+2,d(x3))S(t+1,d(x3))g(n1,nd)+2t+52+1t+21t+1g(n1,nd)+2(nd1)+521nd+1nd+1=g(n,nd+1).

    The equalities hold if only d(x3)=2 and TTTn1,nd. This implies TTTn,nd+1.

    The center of a tree T is the set of vertices with minimum eccentricity (see [14]). A tree T has exactly one or two adjacent center vertices. Let d and r be the diameter and radius of T, respectively. Then

    d={2r1,if T is bicentral,2r,if T has unique center vertex.

    We can easily conclude that SDD(TTn,n2r+2)>SDD(TTn,n2r+1). Thus we have the following Theorem 5.2.

    Theorem 5.2. Let T be a tree of order n with radius r, where 2rn12. Then

    SDD(T)g(n,n2r+2)

    with equality if and only if TTTn,n2r+2.

    The mathematical properties of SDD index deserves further study since it can be applied in detecting the chemical compounds which may have desirable properties. SDD index has been studied extensively since it was proved to be an applicable and viable molecular descriptor in 2018. In this paper, by analyzing the vertex degree of the path whose length is the diameter in a tree and using the method of mathematical induction, we present the maximum SDD indices of trees with given matching number or independence number or domination number or segments or diameter or radius or number of pendant vertices, and identify the corresponding extremal trees. It can be seen that SDD index is in a manner a (local) measure of irregularity. Thus, by adding the pendant vertices as much as possible on the maximum degree vertex to increase the irregularity in a tree with given parameter, one can also explore the extremal trees with other given parameters.

    The authors would like to thank the referees for their careful reading and helpful suggestions. This work was supported by the Shanxi Province Science Foundation for Youths [grant number 201901D211227].

    The authors declare no conflict of interest.



    [1] R. Todeschini, V. Consonni, Handbook of Molecular Descriptors, Wiley-VCH, Weinheim, 2000.
    [2] I. Gutman, B. Furtula (Eds.), Novel Molecular Structure Descriptors - Theory and Applications I, Univ. Kragujevac, Kragujevac, 2010.
    [3] I. Gutman, B. Furtula (Eds.), Novel Molecular Structure Descriptors - Theory and Applications II, Univ. Kragujevac, Kragujevac, 2010.
    [4] D. Vukičević, M. Gašperov, Bond additive modeling 1. Adriatic indices, Croat. Chem. Acta., 83 (2010), 243–260.
    [5] A. Vasilyev, D. Vukičević, MathChem: a Python package for calculating topological indices, MATCH Commun. Math. Comput. Chem., 71 (2014), 657–680.
    [6] B. Furtula, K. C. Das, I. Gutman, Comparative analysis of symmetric division deg index as potentially useful molecular descriptor, Int. J. Quantum Chem., 118 (2018), e25659. doi: 10.1002/qua.25659
    [7] C. K. Gupta, V. Lokesha, S. B. Shwetha, On the symmetric division deg index of graph, Southeast Asian Bull. Math., 40 (2016), 59–80.
    [8] C. K. Gupta, V. Lokesha, S. B. Shwetha, P. S. Ranjini, Graph operations on the symmetric division deg index of graphs, Palest. J. Math., 6 (2017), 280–286.
    [9] Y. Pan, J. Li, Graphs that minimizing symmetric division deg index, MATCH Commun. Math. Comput. Chem., 82 (2019), 43–55.
    [10] K. C. Das, M. Matejic, E. Milovanovic, Bounds for symmetric division deg index of graphs, Filomat, 33 (2019), 683–698. doi: 10.2298/FIL1903683D
    [11] M. Ghorbani, S. Zangi, N. Amraei, New results on symmetric division deg index, J. Appl. Math. Comput., 65 (2021), 161–176. doi: 10.1007/s12190-020-01386-9
    [12] A. Ali, S. Elumalai, T. Mansour, On the symmetric division deg index of molecular graphs, MATCH Commun. Math. Comput. Chem., 83 (2020), 205–220.
    [13] A. Vasilyev, Upper and lower bounds of symmetric division deg index, Iran. J. Math. Chem., 2 (2014), 91–98.
    [14] A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math., 66 (2001), 211–249. doi: 10.1023/A:1010767517079
    [15] J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, Elsevier, New York, 1976.
    [16] L. Sun, R. Chen, The second Zagreb index of acyclic conjugated molecules, MATCH Commun. Math. Comput. Chem., 60 (2008), 57–64.
    [17] O. Ore, Theory of Graphs, AMS, Providence, 1962.
    [18] J. F. Fink, M. S. Jacobson, L. F. Kinch, J. Roberts, On graphs having domination number half their order, Period. Math. Hungar, 16 (1985), 287–293. doi: 10.1007/BF01848079
    [19] S. Noureen, A. Ali, A. A. Bhatti, On the extremal Zagreb indices of n-vertex chemical trees with fixed number of segments or branching vertices, MATCH Commun. Math. Comput. Chem., 84 (2020), 513–534.
  • This article has been cited by:

    1. Jianwei Du, Xiaoling Sun, Extremal symmetric division deg index of molecular trees and molecular graphs with fixed number of pendant vertices, 2022, 434, 00963003, 127438, 10.1016/j.amc.2022.127438
    2. Jianwei Du, Xiaoling Sun, On bond incident degree index of chemical trees with a fixed order and a fixed number of leaves, 2024, 464, 00963003, 128390, 10.1016/j.amc.2023.128390
    3. Hechao Liu, Yufei Huang, Sharp bounds on the symmetric division deg index of graphs and line graphs, 2023, 42, 2238-3603, 10.1007/s40314-023-02428-1
    4. Akbar Ali, Sneha Sekar, Selvaraj Balachandran, Suresh Elumalai, Abdulaziz M. Alanazi, Taher S. Hassan, Yilun Shang, Graphical edge-weight-function indices of trees, 2024, 9, 2473-6988, 32552, 10.3934/math.20241559
    5. W. Tamilarasi, B. J. Balamurugan, QSPR and QSTR analysis to explore pharmacokinetic and toxicity properties of antifungal drugs through topological descriptors, 2025, 15, 2045-2322, 10.1038/s41598-025-01522-0
  • Reader Comments
  • © 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(3090) PDF downloads(160) Cited by(5)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog