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
[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)=∑uv∈E(G)(min{dG(u),dG(v)}max{dG(u),dG(v)}+max{dG(u),dG(v)}min{dG(u),dG(v)})=∑uv∈E(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 G−uv the graph arising from G by deleting the edge uv∈E(G). The subetaaph of G obtained by deleting the vertex x (x∈V(G)) and its incident edges is denoted by G−x. Let Pn and Sn be the n-vertex path and the n-vertex star, respectively.
A matching in G is a subset M⊆E(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 V′⊆V(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 x∈V(G) is defined as εG(x)=max{dG(x,y)|y∈V(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 TT∗n,m be the tree of order n obtained from Sn−m+1 by attaching one pendant edge to each of certain m−1 pendant vertices of Sn−m+1.
Let
S(x,y)=yx+xy, where x,y≥1, |
and
f(n,x)=(n−x)(n−3x2+12)+52(x−1)+n−1n−x, where n≥2, x≥1 and x≤n2. |
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+1−xt+1x, where x,t≥1. Then ft(x) is decreasing for x.
Lemma 2.2. Let h(t)=t+1t−1t+1, where t≥1. Then h(t) is increasing for t.
Lemma 2.3. Let T be a tree. If dT(x,z) is maximum, where x,z∈V(T), then z is a pendant vertex.
Lemma 2.4. Let T∈TT2m,m and y∈V(T). Then ∣NT(y)∩PV(T)∣≤1.
Lemma 2.5. [16] Let T∈TT2m,m. If x,z∈V(T) and dT(x,z) is maximum, then z is adjacent to a vertex of degree two.
Theorem 2.6. Let T∈TT2m,m, where m≥1. Then
SDD(T)≤f(2m,m)=m22+3m−1m−12 |
with equality only when T≅TT∗2m,m.
Proof. By induction on m. If m=1, T≅TT∗2,1 and SDD(T)=2=f(2,1).
Suppose the theorem holds for all trees on fewer than 2m≥4 vertices with a perfect matching. Let x be a vertex satisfying dT(x,z)=max{dT(x,y),y∈V(T)}. Since T∈TT2m,m and |V(T)|=2m≥4, then dT(x,z)≥3 (notice that dT(x,z)=3 only if T≅P4≅TT∗4,2 holds). By Lemma 2.3, it follows that z is a pendant vertex. Let uz∈E(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 T≅P4≅TT∗4,2). We discuss in two cases.
Case 1. vw∉M.
In this case, there exists w′∈NT(w) and vi∈NT(v) such that ww′∈M and vvi∈M, where i≠1. Assume without loss of generality that vvt∈M. Thus it can be seen that vt is a pendant vertex. Otherwise, there exists vertex v′t∈NT(vt)∖{v}. By Lemma 2.4, v′t is a pendant vertex. Since T∈TT2m, we have vtv′t∈M, which contradicts vvt∈M. By Lemma 2.5, we have dT(vi)=2, 1≤i≤t−1. Let NT(vi)∖{v}={zi}, 1≤i≤t−1, where z1=z. Notice that vizi∈M, 1≤i≤t−1. Set T′=T−v1−z1. Thus T′∈TT2(m−1),m−1. 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))+t−1∑i=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)+t−1∑i=2[S(2,dT(v))−S(2,dT(v)−1)]+S(1,dT(v))−S(1,dT(v)−1)≤f(2(m−1),m−1)+(t−1)(12+2t+1−2t)+2t+1+t2+12+52+1+1t+1−1t=f(2(m−1),m−1)+t+1t−1t+1+72≤f(2(m−1),m−1)+m−1+1m−1−1m+72=f(2m,m) |
since t≤m−1. With the equalities hold only if SDD(T′)=f(2(m−1),m−1), t=m−1, dT(w)=2 and V(T)={w,w′,v,vt}∪{v1,v2,⋯, vt−1}∪{z1,z2,⋯,zt−1}. It implies that T′≅TT∗2(m−1),m−1, and T≅TT∗2m,m.
Case 2. vw∈M.
Note that (NT(v)∖{w})∩PV(T)=∅. Otherwise, for y′∈(NT(v)∖{w})∩PV(T), y′ is not M-saturated, which contradicts T∈TT2m,m. Thus we have dT(vi)≥2, 1≤i≤t. In view of Lemma 2.3, we can get that (NT(vi)∖{v})⊂PV(T), 1≤i≤t. And by Lemma 2.5, we have dT(vi)=2, 1≤i≤t. Let NT(vi)∖{v}={zi}, 1≤i≤t, where z1=z. Notice that vizi∈M, 1≤i≤t. Set T′=T−v1−z1. Thus T′∈TT2(m−1),m−1. 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)]+t∑i=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)]+t∑i=2[S(2,dT(v))−S(2,dT(v)−1)]+S(2,dT(v))+S(2,1)≤f(2(m−1),m−1)+(1t+1−1t+1)+(t−1)(12+2t+1−2t)+2t+1+t+12+52=f(2(m−1),m−1)+t+1t−1t+1+72≤f(2(m−1),m−1)+m+1m−1−1m+52=f(2m,m) |
since t≤m−1. With equalities hold only if SDD(T′)=f(2(m−1),m−1), dT(w)=1, t=m−1 and V(T)={w,v}∪{v1,v2,⋯,vt}∪{z1,z2,⋯,zt}. It implies that t=1, w=x and T′≅TT∗2,1. Therefore we have T≅TT∗4,2.
Lemma 2.7. Let l(s,t)=32s+t−1s−1−ts=32s+t−ss(s−1), where s,t≥2 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
∂l∂s=32−t−1(s−1)2+ts2=32+s2−(2s−1)ts2(s−1)2>32+s2−(2s−1)s(s−1)2s2=32−1(s−1)s≥32−12>0, |
then l(s,t) is increasing for s.
Theorem 2.8. Let T∈TTn,m. Then
SDD(T)≤f(n,m). |
The equality holds only when T≅TT∗n,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=x1x2⋯xd+1 a path of length d, where d is the diameter of T. If d≤2, then T≅Sn≅TT∗n,1 and SDD(T)=f(n,1). In what follows, we suppose d≥3. By Lemma 2.3, we can see that x1 is a pendant vertex. Denote NT(x2)={x3,u1,u2,⋯,ur−1} and NT(x3)={x2,x4,v1,v2,⋯,vs−2}, where r,s≥2 and u1=x1. It is evident that dT(ui)=1 (1≤i≤r−1). We discuss in two cases.
Case 1. x2x3∈M.
Now u1=x1 is not M-saturated. Set T1=T−u1. Then T1∈TTn−1,m. Since there exist at least m−1 edges for each matching in T−{x2,x3,u1,u2,⋯,ur−1}, then n−(r+1)≥2(m−1), that is r≤n−2m+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,r−1)+(r−2)(S(1,r)−S(1,r−1))≤SDD(T1)+S(1,r)+S(2,r)−S(2,r−1)+(r−2)(S(1,r)−S(1,r−1))≤f(n−1,m)+2r−32−1r−1+1r≤f(n−1,m)+2(n−2m+1)−32−1n−2m+1n−2m+1=f(n,m)−2n+52m+12−n−1n−m+n−2n−m−1+2(n−2m+1)−32−1n−2m+1n−2m+1=f(n,m)−32m−n−1n−m+n−2n−m−1−1n−2m+1n−2m+1+1<f(n,m)−32m+m−1(n−m)(n−m−1)+1<f(n,m)−32m+32<f(n,m). |
Case 2. x2x3∉M.
Since M is an m-matching in T, now there is ui∈NT(x2) with x2ui∈M. Without loss of generality, assume that x2u1∈M.
Case 2.1. r=2.
Set T2=T−u1−x2. Then T2∈TTn−2,m−1.
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(n−2,m−1)+S(2,2)−S(2,1)+2+52=f(n−2,m−1)+4=f(n,m)−32n+2m−n−1n−m+n−3n−m−1+32=f(n,m)−32n+2m−n−2m+1(n−m−1)(n−m)+32≤f(n,m)−32n+2m+32≤f(n,m)−32(2m+1)+2m+32≤f(n,m)−m<f(n,m). |
Case 2.1.2. s≥3.
Without loss of generality, we suppose that d(v1)=d(v2)=⋯=d(vt)=1 and d(vt+1), d(vt+2),⋯,d(vs−2)≥2. If d=3, then d(x4)=1, d(v1)=d(v2)=⋯=d(vs−2)=1 and this implies T≅TT∗n,2. So we assume that d≥4. Since there exist at least m−3 M-saturated vertices in V(T)∖{x1,x2,⋯,x5,v1,v2,⋯,vs−2}, then |V(T)|=n≥|{x1,x2,⋯,x5,v1,v2,⋯,vs−2}|+m−3=s+m, that is s≤n−m.
Case 2.1.2.1. t≤1.
By induction hypothesis and Lemmas 2.1, 2.2, it follows that
SDD(T)=SDD(T2)+S(d(x4),s)−S(d(x4),s−1)+S(d(v1),s)−S(d(v1),s−1)+s−2∑i=2(S(d(vi),s)−S(d(vi),s−1))+S(2,s)+S(2,1)≤f(n−2,m−1)+(s−2)(S(2,s)−S(2,s−1))+S(1,s)−S(1,s−1)+S(2,s)+S(2,1)=f(n−2,m−1)+s+52−1s+1s−1≤f(n,m)−32n+2m−52−n−1n−m+n−3n−m−1+n−m+52−1n−m+1n−m−1=f(n,m)−n2+m−n−2m(n−m)(n−m−1)<f(n,m)−n2+m<f(n,m). |
Case 2.1.2.2. t≥2.
Since there are at least t−1 pendant vertices which are not M-saturated, then n−(t−1)≥2m, that is t≤n−2m+1. Set T3=T−v1. Then T3∈TTn−1,m. By induction hypothesis and Lemmas 2.1, 2.7, it follows that
SDD(T)=SDD(T3)+S(d(x4),s)−S(d(x4),s−1)+S(2,s)−S(2,s−1)+S(1,s)+t∑i=2(S(1,s)−S(1,s−1))+s−2∑i=t+1(S(d(vi),s)−S(d(vi),s−1))≤f(n−1,m)+(s−t)(S(2,s)−S(2,s−1))+S(1,s)+(t−1)(S(1,s)−S(1,s−1))=f(n−1,m)+t2+32(s−2)+2−2s−t−1s−1+2s−ts=f(n−1,m)+t2+32s−ts+t−1s−1−1≤f(n−1,m)+t2+32(n−m)−tn−m+t−1n−m−1−1≤f(n−1,m)+n−2m+12+32(n−m)−n−2m+1n−m+n−2mn−m−1−1=f(n,m). |
The equalities hold only if d(x4)=2, t=n−2m+1, s=n−m and T3≅TT∗n−1,m. This implies T≅TT∗n,m.
Case 2.2. r≥3.
In this case, u2,⋯,ur−1 is not M-saturated and n−(r−2)≥2m, that is r≤n−2m+2. Since d≥3, then x3x4∈E(T). Set T4=T−u2. Then T4∈TTn−1,m. If m=2, then T≅TT∗n,2. If m≥3, By induction hypothesis and Lemmas 2.1, 2.2, it follows that
SDD(T)=SDD(T4)+S(d(x3),r)−S(d(x3),r−1)+S(1,r)−S(1,r−1)+S(1,r)+r−1∑i=3(S(1,r)−S(1,r−1))≤f(n−1,m)+S(2,r)−S(2,r−1)+(r−2)(S(1,r)−S(1,r−1))+S(1,r)=f(n−1,m)+2r+1r−1r−1−32≤f(n−1,m)+2(n−2m+2)+1n−2m+2−1n−2m+1−32<f(n−1,m)+2(n−2m+2)−32=f(n,m)−32m+3+(m−1)(1n−m−1−1n−m)<f(n,m)−32m+3+13<f(n,m) |
since 1n−m−1−1n−m<1m−1−1m for n−m>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 T≅TT∗n,n−β.
It is evident that κ(T)=1 for a tree T on n vertices if and only if T≅Sn. 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 T∈TTn,κ with Δ(T)=n−κ, then T≅TT∗n,κ.
Theorem 3.1. Let T∈TTn,κ, where n≥3 and κ≤n2. Then
SDD(T)≤f(n,κ). |
The equality holds only when T≅TT∗n,κ.
Proof. If n=3, T≅P3≅TT∗3,1 and SDD(P3)=5=f(3,1). If n=4, T≅P4≅TT∗4,2 or S4≅TT∗4,1, and SDD(P4)=7=f(4,2), SDD(S4)=10=f(4,1). Now, suppose n≥5 and the theorem holds for any T on fewer than n vertices. We use Pd+1=x1x2⋯xd+1 to denote a path of length d, where d is the diameter of T. If d=2, then T≅Sn and κ(Sn)=1, the result is ture. So in what follows, we suppose that κ(T)≥2. Denote NT(x2)={x1,x3,u1,u2,⋯,ur−2} and NT(x3)={x2,x4,v1,v2,⋯,vs−2}, where r,s≥2. 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(r−1,s)+(r−2)(S(1,r)−S(1,r−1))≤f(n−1,κ)+S(1,r)+S(r,2)−S(r−1,2)+(r−2)(S(1,r)−S(1,r−1))=f(n,κ)−2n+52κ+12+n−2n−κ−1−n−1n−κ+2r+1r−1r−1−32. |
Since κ≤n−(r−2)2, that is r≤n−2κ+2, by Lemma 2.2, it follows that
SDD(T)≤f(n,κ)−2n+52κ+12+n−2n−κ−1−n−1n−κ+2(n−2κ+2)+1n−2κ+2−1n−2κ+1−32=f(n,κ)−32κ+3+n−2n−κ−1−n−1n−κ+1n−2κ+2−1n−2κ+1. |
If κ=2, SDD(T)≤f(n,κ). The equalities hold if only s=2 and n=r+2. This implies T≅TT∗n,2. If κ≥3, we have
SDD(T)<f(n,κ)−32κ+3+n−2n−κ−1−n−1n−κ=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 T≅TT∗n,κ, and the theorem holds. So in what follows, we assume that s≤n−κ−1. By the case 1 above, assume that d(vi)≤2, i∈{1,2,⋯,s−2}. If x4 is a pendant vertex or a support vertex with d(x4)=2, then T≅TT∗n,κ. In other cases, without loss of generality, let d(v1)=⋯=d(vs1)=1, d(vs1+1)=⋯=d(vs1+s2)=2, where s1+s2=s−2.
Case 2.1. s1≥2.
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(s−1,2)+S(s,1)+S(s,d(x4))−S(s−1,d(x4))+(s1−1)(S(s,1)−S(s−1,1))+s2(S(s,2)−S(s−1,2))≤SDD(T2)+s+1s+(s1−1)(1+1s−1s−1)+(s2+2)(12+2s−2s−1)≤f(n,κ)−2n+52κ+12−n−1n−κ+n−2n−κ−1+32s+s12−1+s1−ss(s−1)<f(n,κ)−2n+52κ+12−n−1n−κ+n−2n−κ−1+32s+s12−1. |
Since s≤n−κ−1, κ≤n−(s1−1)2 and −n−1n−κ+n−2n−κ−1=κ−1(n−κ)(n−κ−1)<1. Therefore
SDD(T)<f(n,κ)−2n+52κ+12+32(n−κ−1)+n−2κ+12=f(n,κ)−12<f(n,κ). |
Case 2.2. s1≤1.
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(s−1,d(x4))+S(s,d(v1))−S(s−1,d(v1))+S(s,2)+S(1,2)+(s−3)(S(s,2)−S(s−1,2))≤SDD(T3)+1+1s−1s−1+(s2+2s)+52+(s−2)(12+2s−2s−1)≤f(n−2,κ−1)+s+52+1s−1−1s≤f(n,κ)−32n+2κ−52−n−1n−κ+n−3n−κ−1+s+52+1s−1−1s. |
Since s≤n−κ−1, 1s−1−1s=1s(s−1)≤12 and −n−1n−κ+n−3n−κ−1=2κ−n−1(n−κ)(n−κ−1)<0. Therefore
SDD(T)<f(n,κ)−32n+2κ+n−κ−1+12=f(n,κ)−n2+κ−12≤f(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,n−1 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 T∈TT(1)n,n−1. Furthermore, TT(2)n,2 is a path, TT(2)n,n−1 is star. Thus we only consider the case of 3≤s≤n−2 (3≤p≤n−2, respectively) when T∈TT(1)n,s (T∈TT(2)n,p, respectively). Let
g(n,x)=2n+x2−52x−12+1x, where n≥5 and 2≤x≤n−2. |
Let TTn,s be the tree of order n obtained from Pn−s+1 by attaching s−1 pendant edge to one pendant vertex of Pn−s+1.
Theorem 4.1. Let T∈TT(1)n,s, where n≥5 and 3≤s≤n−2. Then
SDD(T)≤g(n,s) |
with equality only when T≅TTn,s.
Proof. By induction on n. If n=5, then s=3, T≅TT5,3 and SDD(TT5,3)=g(5,3), the result holds. Now, suppose n≥6 and the result holds for any T of order n−1. Denoted by Pd+1=x1x2⋯xd+1 a path of length d, where d is the diameter of T. If d=2, then T≅Sn. Therefore d≥3. Set T′=T−{x1}.
Case 1. d(x2)=2.
Then T′∈TT(1)n−1,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(n−1,s)+S(2,2)=g(n,s). |
With equality only when d(x3)=2 and T′≅TTn−1,s. This implies T≅TTn,s.
Case 2. d(x2)≥3.
Denote NT(x2)∖{x1,x3}={u1,u2,⋯,ut}, where t≥1. Then u1,u2,⋯,ut are pendant vertices and T′∈TT(1)n−1,s−1. Since t≤s−2, by induction hypothesis and Lemmas 2.1, 2.2, it follows that
SDD(T)=SDD(T′)+S(1,t+2)+t∑i=1(S(t+2,d(ui))−S(t+1,d(ui)))+S(t+2,d(x3))−S(t+1,d(x3))≤g(n−1,s−1)+S(1,t+2)+t(S(t+2,1)−S(t+1,1))+S(t+2,2)−S(t+1,2)=g(n−1,s−1)+2t+52+1t+2−1t+1≤g(n−1,s−1)+2(s−2)+52+1s−1s−1=g(n,s). |
The equalities hold if only d(x3)=2 and T′≅TTn−1,s−1. This implies T≅TTn,s.
By a similar proof of Theorem 4.1, we can get Theorem 4.2.
Theorem 4.2. Let T∈TT(2)n,p, where n≥5 and 3≤p≤n−2. Then
SDD(T)≤g(n,p) |
with equality if and only if T≅TTn,p.
Let TT(3)n,d be the n-vertex trees with diameter d. Since TT(3)n,2≅Sn, so we consider the case of 3≤d≤n−1 when T∈TT(3)n,d.
Theorem 5.1. Let T∈TT(3)n,d, where 3≤d≤n−1. Then
SDD(T)≤g(n,n−d+1) |
with equality only when T≅TTn,n−d+1.
Proof. By induction on n. If n=4, then d=3, T≅P4≅TT4,2 and SDD(P4)=g(4,2), the result holds. Now, suppose n≥5 and the theorem holds for any T on n−1 vertices. We use Pd+1=x1x2⋯xd+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 1≤n−d≤n−3, 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(n−1,n−d)+S(2,2)=g(n,n−d+1)−2(n−d)+32−1n−d+1+1n−d≤g(n,n−d+1)−2+32+1−12≤g(n,n−d+1). |
The equalities hold if only d(x3)=2, n−d=1 and T′≅TTn−1,n−d. But these cannot hold together, so SDD(T)<g(n,n−d+1).
If the diameter of T′ is d−1, by induction hypothesis and Lemma 2.1, it follows that
SDD(T)≤g(n−1,n−d+1)+S(2,2)=g(n,n−d+1). |
The equality holds if only d(x3)=2 and T′≅TTn−1,n−d+1. This implies T≅TTn,n−d+1.
Case 2. d(x2)≥3.
Denote NT(x2)∖{x1,x3}={u1,u2,⋯,ut}, where t≥1 and u1,u2,⋯,ut are pendant vertices. Then the diameter of T′ is d. Since t≤n−(d+1), by induction hypothesis and Lemmas 2.1, 2.2, we have
SDD(T)=SDD(T′)+S(1,t+2)+t∑i=1(S(t+2,d(ui))−S(t+1,d(ui)))+S(t+2,d(x3))−S(t+1,d(x3))≤g(n−1,n−d)+2t+52+1t+2−1t+1≤g(n−1,n−d)+2(n−d−1)+52−1n−d+1n−d+1=g(n,n−d+1). |
The equalities hold if only d(x3)=2 and T′≅TTn−1,n−d. This implies T≅TTn,n−d+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={2r−1,if T is bicentral,2r,if T has unique center vertex. |
We can easily conclude that SDD(TTn,n−2r+2)>SDD(TTn,n−2r+1). Thus we have the following Theorem 5.2.
Theorem 5.2. Let T be a tree of order n with radius r, where 2≤r≤n−12. Then
SDD(T)≤g(n,n−2r+2) |
with equality if and only if T≅TTn,n−2r+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. |
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 |