给定悬挂点个数的分子树的ISDD指数的极值.pdf

2024 年 第 45 卷 第 1 期（总第 213 期）Vol.45 No.1 2024（Sum No.213）中 北 大 学 学 报（自然科学版）JOURNAL OF NORTH UNIVERSITY OF CHINA（NATURAL SCIENCE EDITION）给定悬挂点个数的分子树的ISDD指数的极值赵芳方，邵燕灵（中北大学 数学学院，山西 太原 030051）摘 要：设G=(V(G)，E(G)为n阶连通图，其顶点集为V(G)，边集为E(G)，用deg(x)表示顶点x的度，则图G的反对称分割指数为ISDD(G)=xyE()G()deg()x deg()ydeg()x2+deg()y2。本文主要采用不等式和分类讨论法对具有固定悬挂点的分子树的ISDD指数进行了研究，分别讨论了悬挂点个数为偶数和悬挂点个数大于等于3时分子树的ISDD指数的极值，分子树是指顶点度不超过4的树。首先，确定了当悬挂点个数为偶数时，分子树中反对称分割指数为最小值，此时，ISDD(MT)=12n-3185p-110；其次，确定了当悬挂点个数大于等于3时，分子树中反对称分割指数为最大值，此时，ISDD(MT)=12n-965p-12，并刻画了达到ISDD指数极值的分子树。关键词：图；反对称分割指数（ISDD指数）；悬挂点；分子树中图分类号：O178 文献标识码：A doi:10.3969/j.issn.1673-3193.2024.01.004引用格式：赵芳方，邵燕灵.给定悬挂点个数的分子树的ISDD指数的极值 J.中北大学学报（自然科学版），2024，45（1）：30-35.ZHAO Fangfang，SHAO Yanling.Extremal ISDD index of molecular trees with fixed number of pendent vertices J.Journal of North University of China（Natural Science Edition），2024，45（1）：30-35.Extremal ISDD Index of Molecular Trees with Fixed Number of Pendent VerticesZHAO Fangfang，SHAO Yanling（School of Mathematics，North University of China，Taiyuan 030051，China）Abstract：Let G=(V(G)，E(G)be a connected graph of order n，V(G)be vertex set of G，E(G)be edge set of G，deg(x)be degree of the vertex x.The inverse symmetric division deg index of G is ISDD(G)=xyE()G()deg()x deg()ydeg()x2+deg()y2.Inequality and classification discussion are used to study the ISDD(G)of molecular tree with fixed number of pendent vertices，respectively，the extreme value of the ISDD index of the molecular tree with the number of pendent vertices is even number and the number of pendent vertices is more than or equal to 3 are discussed，the tree whose vertex degree is less than 4 is called molecular tree.Firstly，the minimum value of the inverse symmetric division deg index of G is 文章编号：1673-3193（2024）01-0030-06收稿日期：2022-11-18基金项目：山西省自然科学基金资助项目（201901D211227）作者简介：赵芳方（1997-），女，硕士，主要从事图论、组合数学方向的研究。通信作者：邵燕灵（1963-），女，教授，博士，主要从事图论、组合数学方向的研究。E-mail：。（总第 213 期）给定悬挂点个数的分子树的ISDD指数的极值（赵芳方等）determined when the number of pendent vertices is even，that is ISDD(MT)=12n-3185p-110.Secondly，when the number of pendent vertices is greater than or equal to 3，the maximum value of the inverse symmetric division deg index of G in the molecular tree is determined，that is ISDD(MT)=12n-965p-12，and the molecular tree of ISDD index reaching the extreme value is described.Key words：graph；inverse symmetric division deg index（ISDD index）；pendent vertex；molecular tree0引 言本文所考虑的图均为简单无向连通图。设G=(V(G)，E(G)为n阶m条边的无向图，其顶点 集 为V(G)=v1,v2,vn，边 集 为E(G)，deg(x)为顶点x的度，xv1,v2,vn；用e=xy表示其端点为x，y的边，若deg(x)=1，则称x为悬挂点。用nk表示度为k的顶点个数，用mi，j表示图G中满足deg(x)=i，deg(y)=j的边xy的个数1。设G+xy和G-xy分别表示图G通过添加一条边xyE(G)和删掉一条边xyE(G)而得到的图，其中，x,yV(G)。用Sn表示n阶星图，用Pr=w0w1wr表示在图G中满足deg(wi)=2(i=1,2,r-1)（除r=1外）的路，如果Pr满足deg(w0)=1和deg(wr)3，则称Pr为G的一条悬挂路2。分子图是顶点最大度不大于4的图，它可用于描述化合物的分子结构，在数学与化学中发挥着重要作用35。图不变量是从图到正实数的数值函数，代表了一种重要的分子描述符6，它可以通过一些新的软件计算，比如Python7。图G的反对称分割指数（ISDD指数）是基于顶点度的一种图不变量，是 Ghorbani 等提出的一个新分子拓扑指数8，其定义为ISDD(G)=xyE()Gdeg(x)deg(y)deg(x)2+deg(y)2。（1）基于顶点度的拓扑指数是一类非常重要的拓扑 指 数，其 中，Zagreb 指 数、Randi 指 数、Forgotten 指数、GA 指数、AG 指数、Harmonic指数、Inverse sum indeg指数、对称分割指数7等已经在研究化学相关问题的QSPR/QSAR中得到了广泛应用6，916。ISDD指数可用于检测可能具有优良性质的化合物，它的数学性质值得被进一步研究。ISDD指数被证明是一种适用和可行的分子描述符。Akbar Ali等研究了单圈图的ISDD指数，在具有固定顺序的所有连通单圈图集合中找出具有最大和最小ISDD指数的图17。程宇等18研究了ISDD指数和其他指数的关系，并证明了在一定条件下，ISDD指数和对称分割指数是线性相关的。这些研究为深入研究ISDD指数的其他性质奠定了坚实的基础。本文利用不等式计算出具有固定悬挂点个数的分子树的ISDD指数的最大及最小值，并进一步刻画了达到ISDD指数极值的分子树。1具有固定悬挂点个数的分子树的ISDD指数设MT是有p个悬挂点的n阶分子树。显然，p=n1，那么p+n2+n3+n4=n,p+2n2+3n3+4n4=2m=2()n-1,m1,2+m1,3+m1,4=p,m1,2+2m2,2+m2,3+m2,4=2n2,m1,3+m2,3+2m3,3+m3,4=3n3,m1,4+m2,4+m3,4+2m4,4=4n4。（2）由式（1）可得ISDD(MT)=25m1,2+310m1,3+417m1,4+12m2,2+613m2,3+25m2,4+12m3,3+1225m3,4+12m4,4。（3）由分子树MT中所有度等于或大于3的顶点诱导而成的子图，称为MT的分支子图，也就是说，它是从MT中去掉度小于3的顶点和与它们相关联的边而产生的子图。用()1n,p（p是偶数），()2n,p来表示两类有p个悬挂点的n阶分子树。分子树()1n,p如图 1 所示，其中，n9，p是偶数，6p n+32。它们由p-22个星图S5组312024 年第 1 期中 北 大 学 学 报（自然科学版）成，星图S5由路连接在一起，有些路的长度可能为0。显 然，m1,4=p，m2,2=n-2p+3，m2,4=p-4，n3=0，n1=p，n2=n-32p+1，n4=12p-1。分子树()2n,p如图 2 所示，其中，n7，3p n+23。它有p-2个最大度为3的点，这些顶点可能与一个度为2的顶点相连，也可能与另一个度为3的顶点相连。显然，m1,2=p,m1,3=0,m2,2=n-3p+2,m2,3=p,m3,3=p-3,n4=0,n1=p,n3=p-2,n2=n-2p+2。1.1具有固定悬挂点个数的分子树的ISDD指数的最小值设n,p是有p个悬挂点的n阶树，通过将p-1个悬挂点与有n-p+1个顶点的一条路的一个端点连接而成。引理 119 设T是有p个悬挂点的n阶树，其中，n5，2pn-2，则ISDD(G)12n-12p+25+2p4+p2-p+11+p2，等式成立，当且仅当Tn,p。根据引理 1 可知，当p4时，在所有具有p个悬挂点的分子树中，n,p是ISDD指数取到最小值的树，下面仅考虑p5的情况。定理 1 设MT是有p个悬挂点的n阶分子树，其中，p5，则ISDD(MT)12n-3185p-110，等 式 成 立，当 且 仅 当MT()1n,p（6p n+32，p是偶数）。证明 对于任意一个有p(p5)个悬挂点的n阶分子树，根据式（2），Xing等20推导出 m1,4=p-m1,2-m1,3,m2,2=n-2p-m1,2-13m1,3-13m2,3+13m3,3+23m3,4+m4,4+3,m2,4=p+m1,2+13m1,3-23m2,3-43m3,3-53m3,4-2m4,4-4。（4）将式（4）代入式（3），有ISDD(MT)=12n-3185p-110+(11170m1，2+8255m1，3+11390m2，3+215m3，3+1175m3，4+15m4，4)，（5）因为m1,2,m1,3,m2,3,m3,3,m3,4,m4,4是非负整数，故ISDD(MT)12n-3185p-110。ISDD(MT)=12n-3185p-110，当 且 仅 当m1,2=m1,3=m2,3=m3,3=m3,4=m4,4=0，此 时m1,4=p，m2,2=n-2p+3，m2,4=p-4。由式（2）可得n3=0，n1=p，n2=n-32p+1，n4=12p-1。故MT()1n,p，其中，p为偶数。得证。1.2具有固定悬挂点个数的分子树的ISDD指数的最大值对于任何具有p=2个悬挂点的n阶分子树MT，是一个n阶路。下面仅考虑p3。引理 2 设MT是一个有p个悬挂点的n阶分子树，其中，p3。如果ISDD(MT)取最大，则MT的分支子图一定是树。证明 对于p=3，在MT中存在唯一度为 3图 1()1n，p（n9，6p n+32，p是偶数）Fig.1 ()1n，p（n9，6p n+32，p is even number）图 2()2n，p（n7，3p n+23）Fig.2 ()2n，p（n7，3p n+23）32（总第 213 期）给定悬挂点个数的分子树的ISDD指数的极值（赵芳方等）的顶点，并且容易看出MT的分支子图是一个树。对于p4，选择MT，使MT具有最大的ISDD值。假设MT的分支子图不是树，则MT必包含两个顶点，分别是度为3或4的x，y点，把它们连接到一条路xu1u2usy，长度为s+12，其中，deg(u1)=deg(u2)=deg(us)=2。设deg(z)=1，z在MT中 的 邻 点 为v，deg(v)2，又因为MT是顶点度不超过4的分子树，所以2d(v)4，deg(x)=3或4，deg(y)=3或4。设IS(，)=2+2，其中，1。设f(x，y)=IS(x，y)-IS(x，2)，其 中，x=deg(x)，y=deg(y)，则当deg（x）=3，deg（y）=3时，f(3，3)=IS(3，3)-IS(3，2)=3332+32-3232+32=12-613=126。（6）当deg（x）=4，deg（y）=3时，f(4，3)=IS(4，3)-IS(4，2)=4342+32-4242+32=1225-225=225，（7）故f(3，3)f(4.3)。当deg（x）=3，deg（y）=4时，f(3，4)=IS(3，4)-IS(3，2)=3432+42-3232+22=1225-613=6325。（8）当deg（x）=4，deg（y）=4时，f(4，4)=IS(4，4)-IS(4，2)=12-4242+22=12-25=110，故f(3，4)ISDD()MT，（12）这与MT的选择是矛盾的，故引理成立。定理 2 假设MT是一个n阶分子树，有p个悬挂点，其中，p3，则ISDD(MT)12n-965p-12，（13）等式成立，当且仅当MT()2n,p。证明 对于任何有p个悬挂点的n阶分子树，根据式（2），Hansen等21推导出 m1,2=p-m1,3-m1,4,m2,2=n-52p+12m1,3+34m1,4-12m2,3-14m2,4+14m3,4+12m4,4+2,m3,3=32p-12m1,3-34m1,4-12m2,3-34m2,4-54m3,4-32m4,4-3。（14）将式（14）代入式（3），得ISDD(MT)=12n-110p-12-(110m1，3+126m2，3+1485m1，4+110m2，4+150m3，4)。（15）选择MT，使得MT取到ISDD指数的最大332024 年第 1 期中 北 大 学 学 报（自然科学版）值。由引理 2 得m3，3+m3，4+m4，4=n3+n4-1。（16）由式（2）中的m1,3+m2,3+2m3,3+m3,4=3n3和m1,4+m2,4+m3,4+2m4,4=4n4，得m1，3+m2，3+m1，4+m2，4=3n3+4n4-2(m3，3+m3，4+m4，4)。（17）由式（16）和式（17）得m1，3+m2，3+m1，4+m2，4=n3+2n4+2。（18）又由式（2）中的p+2n2+3n3+4n4=2(n-1)与p+n2+n3+n4=n得2n4+n3=p-2。（19）将 式（19）代 入 式（18），得m1,3+m2,3+m1,4+m2,4=p，即m2,3=p-m1,3-m1,4-m2,4。代入式（15），得ISDD(MT)=12n-965p-12-(465m1,3+2792210m1,4+465m2,4+150m3,4),（20）故ISDD(MT)12n-965p-12。显然，ISDD(MT)=12n-965p-12，当且仅当m1,3=m1,4=m2,4=m3,4=0，此时m1,2=p，m2,3=p，m2,2=n-3p+2，m3,3=p-3，由式（2）得，n2=n-2p+2，n3=p-2，n4=0。故MT()2n，p。得证。2结 论本文利用分类讨论法，给出了给定悬挂点个数的分子树的ISDD指数的最大值及最小值，并识别出相应的极值树，可以看出ISDD指数在某种程度上是一种（局部的）不规则度量。因此，通过在顶点上添加尽可能多的悬挂点来增加具有给定参数的树的不规则性，也可以探索具有其他给定参数的极树。参考文献：1DU J W，SUN X L.Extremal symmetric division deg index of molecular trees and molecular graphs with fixed number of pendant verticesJ.Applied Mathematics and Computation，2022，434：127438.2BONDY J A，MURTY U S R.Graph theory with applications M.New York：Elsevier，1976.3ALI A，ELUMALAI S，MANSOUR T.On the symmetric division deg index of molecular graphs J.Match Communications in Mathematical&in Computer Chemistry，2020，83：205-220.4XU K，DAS K C.Some extremal graphs with respect to inverse degreeJ.Discrete Applied Mathematics，2016，203：171-183.5FURTULA B，DAS K C，GUTMAN I.Comparative analysis of symmetric division deg index as potentially useful molecular descriptor J.International Journal of Quantum Chemistry，2018，118（17）：e25659.6GUTMAN I，FURTULA B.Novel molecular structure descriptors-theory and applications II M.Serbia：University of Kragujevac，2010.7VASILYEV A，VUKIEVI D.MathChem：a python package for calculating topological indicesJ.Match Communications in Mathematical&in Computer Chemistry，2014，71：657-680.8GHORBANI M，ZANGI S，AMRAEI N.New results on symmetric division deg index J.Journal of Applied Mathematics and Computing，2021，65：161-176.9DAS K C，MATEJIC M，MILOVANOVIC E.Bounds for symmetric division deg index of graphs J.Filomat，2019，33（3）：683-698.10JIANG Y，CHEN X，LIN W.A note on chemical trees with maximal inverse sum indeg index J.Match Communications in Mathematical&in Computer Chemistry，2021，86：29-38.11SUN X L，GAO Y B，DU J W.On symmetric division deg index of unicyclic graphs and bicyclic graphs with given matching number J.AIMS Mathematics，2021，6（8）：9020-9035.12NOUREEN S，ALI A，BHATTI A A.On the extremal Zagreb indices of n-vertex chemical trees with fixed number of segments or branching verticesJ.Match Communications in Mathematical&in Computer Chemistry，2020，84：513-534.13HASNI R,AHMAD JAMRI A A S,ARIF N E,et al.The randic index of trees with given total domination numberJ.Iranian Journal of Mathematical Chemistry,2021,12(4):225-237.14 HU X,ZHANG L.The harmonic index for trees with given domination numberJ.Discrete Mathematics Letters,2022,9:31-37.15 JAVAID M,JAVED S,MEMON S Q.Forgotten index of generalized operations on graphsJ.Journal of Chemistry,2021,2021:1-14.16 胡文静,高玉斌.删边操作下图的Harmonic能量J.中北大学学报(自然科学版),2023,44(2):104-108.34（总第 213 期）给定悬挂点个数的分子树的ISDD指数的极值（赵芳方等）HU Wenjing,GAO Yubin.The harmonic energy after edge deletionJ.Journal of North University of China(Natural Science Edition),2023,44(2):104-108.(in Chinese)17 ALBALAHI A M,ALI A.On the inverse symmetric division deg index of unicyclic graphsJ.Computation,2022,10(10):181-187.18 程宇,邵燕灵.图的 ISDD指数的界J.中北大学学报(自然科学版),2022,43(5):385-389.CHENG Yu,SHAO Yanling.Bounds of ISDD indices of graphsJ.Journal of North University of China(Natural Science Edition),2022,43(5):385-389.(in Chinese)19 DU J W,SUN X L.On symmetric division deg index of trees with given parametersJ.AIMS Mathematics,2021,6(6):6528-6541.20 XING R,ZHOU B,TRINAJSTIC N.Sum-connectivity index of molecular treesJ.Journal of Mathematical Chemistry,2010,48:583-591.21 HANSEN P,MLOT H.Variable neighborhood search for extremal graphs.6.Analyzing bounds for the connectivity indexJ.Journal of Chemical Information and Computer Sciences,2003,43(1):1-14.声明本刊已许可中国知网、万方、维普、超星等数据库以数字化方式复制、汇编、发行、信息网络传播本刊全文。本刊支付的稿酬已包含上述数据库著作权使用费，所有署名作者向本刊提交文章发表之行为视为同意上述声明。如有异议，请在投稿时说明，本刊将按作者说明处理。35