关于Mycielski图补图的一些指标的结果.pdf

关于Mycielski图补图的一些指标的结果冯 旭，马 丽*，冯 娜，王雅慧，热萨莱提 穆海买提（新疆农业大学 数理学院，新疆 乌鲁木齐 830052）摘要：拓扑指标是分子结构的数学描述符，它将分子的形状、大小、分支等结构特征数值化，且计算简便、取值客观，不易受经验和实验的影响，是数学与化学研究中非常活跃的领域之一。研究拓扑指标图不变量可用于描述和预测有机化合物的理化或药理性质。文章研究Mycielski图的补图的两类度距离指标：Schultz指标和修正的Schultz指标。同时，还给出了一些特殊图的Mycielski图及其补图的Lanzhou指标的表达式。关键词：Mycielski图；Schultz指标；修正的Schultz指标；Lanzhou指标中图分类号：O157.5文献标识码：A文章编号：1008-9659（2024）02-0010-07Vol.43，No.2Jun.2024第43卷 第2期2024年6月新疆师范大学学报（自然科学版）Journal of Xinjiang Normal University（Natural Sciences Edition）收稿日期 2023-08-26 修回日期 2023-10-29 基金项目 新疆农业大学大学生创新创业训练计划项目（dxscx2023491）。作者简介 冯 旭（1999-），男，主要从事数学与应用数学方面研究，E-mail：.*通讯作者 马 丽（1991-），女，讲师，主要从事图论及其应用方面研究，E-mail：.拓扑指标是与图结构相关的数值，它是分子图的一个拓扑不变量。将分子拓扑指标与化合物相应的物理性质、化学反应或生物活性建立一种对应关系，进行相关性分析，在某种程度上达到解释和预测分子理化性质的目的。为了能与分子的理化性质建立良好的相关性，许多学者在距离、度、计数和谱等基础上定义了多种拓扑指标，目前提出的拓扑指标已经有上百种。在这上百种指标中，有第一Zagreb指标和第二Zagreb指标1-2，分别定义为M1(G)=vi V()Gd2G()vi=vivj E()GdG()vi+dG()vj和M2()G=vivj E()GdG()vidG()vj后来，Doslic 3给出了第一Zagreb余指标和第二Zagreb余指标分别为-M1()G=vivj E()GdG()vi+dG()vj和-M2()G=vivj E()GdG()vidG()vj 更多相关指标请参考文献 4-8。另外，基于顶点度距离的拓扑指数9在图论中的研究也备受研究者的青睐。例如，图G的Schultz指标被定义为S()G=vi,vj V()GdG()vi,vj()dG()vi+dG()vj图G的修正Schultz指标或Gutman指标记为S*()G，被定义为10冯 旭，等：关于Mycielski图补图的一些指标的结果S*()G=vi,vj V()GdG()vi,vj()dG()vidG()vj最近，Vukicevic 等人为分子图G引入了一个新的拓扑指标，称Lanzhou指标10，即Lz()G=u V()Gdud2u其中，du和du分别表示图 G 中点 u 的度和图 G 的补图G中点 u 的度。Lanzhou 指标 Lz（G）也可表示为()n-1 M1()G-F()G,其中n是G中的顶点数，M1（G）表示G的第一Zagreb指标且F（G）表示G的Forgotten指标11-13，即F()G=vi V()Gd3G()vi=vivj E()Gd2G()vi+d2G()vj在文献 14 中已经给出了Mycielski图的两类度距离指标Schultz指标和Gutman指标的界。文章将主要讨论Mycielski图的补图的两类度距离指标Schultz指标和Gutman指标，并给出了具体表达式。同时，还给出了一些特殊图的Mycielski图及其补图的Lanzhou指标的表达式。1 基础知识设G=()V()G,E()G是含有点集为V()G且边集E()G的简单连通图。在图G中，dG(u)表示点u的度，dG(u,v)表示点u和点v的距离。图G的补图G具有相同的顶点集V()G，且G中的两个顶点相邻当且仅当在G中不相邻。图G的Mycielski图15记为(G)，其顶点集为V V u，其中V=x:x V，边集为E xy:xy Exu:x V，其中称x为x的拷贝点，称u点为(G)的根点。引理1 设G是含有n个点和m条边的简单连通图，则有vi,vj V()G()dG()vi+dG()vj=2m()n-1引理25 设G是含有n个点和m条边的简单连通图，则有-M1()G=vivj E()G()dG()vi+dG()vj=2m()n-1-M1()G引理36 设G是含有n个点和m条边的简单连通图，则有-M2()G=2m2-M2()G-12M1()G2 主要结论命题1 设G是含有n个点和m条边的简单连通图，则其Mycielski图(G)与Mycielski图的补图(G)中任意一点u的度和任意点对u,v的距离有：（1）若u V()(G)，则有Mycielski图(G)与Mycielski图的补图(G)中任意一点u的度分别为d()G()u=2dG()vi,u=vidG()vi+1,u=xin,u=z和 d()G()u=2n-2dG()vi,u=vi2n-1-dG()vi,u=xin,u=z（2）若u,v V()(G)，则有Mycielski图(G)与Mycielski图的补图(G)中的任意两点u和v的距离分别为11新疆师范大学学报（自然科学版）2024年()i d()G()u,v=2,u=xi,v=xjdG()vi,vj,u=vi,v=vj,dG()vi,vj 34,u=vi,v=vj,dG()vi,vj 4 ()ii d()G()u,v=2,u=vi,v=xj,i=jdG()vi,vj,u=vi,v=xj,i j,dG()vi,vj 23,u=vi,v=xj,i j,dG()vi,vj 3 ()iii d()G()u,v=1,u=xi,v=z2,u=vi,v=z和 ()iv d()G()u,v=1,u=vi,v=vj,dG()vi,vj 1,vivj E()G2,u=vi,v=vj,dG()vi,vj=1,vivj E()G1,u=xi,v=xj ()v d()G()u,v=1,u=vi,v=xj,i=j1,u=vi,v=xj,i j,dG()vi,vj 12,u=vi,v=xj,i j,dG()vi,vj 1 ()vi d()G()u,v=1,u=vi,v=z2,u=xi,v=z显然，在(G)中的任意两点u和v的最大距离是4，在(G)中的任意两点u和v的最大距离是2.2.1 Mycielski图补图的Schultz指标和修正Schultz指标定理 1 设G是含有 n 个点和 m 条边的简单连通图，则其 Mycielski 图的补图(G)的 Schultz 指标为 S(G)=8n3+3n2-n-4m-5M1(G).证明 在(G)中，任意两点u和v分别是以下五种类型的点对：类型1：vi,vj是图G的点，类型2：xi,xj是图G点的拷贝点，类型3：vi,xj是图G的点和图G点的拷贝点，类型4：vi,z是图G的点和根点，类型5：xi,z是图G的拷贝点和根点。（1）若u和v是类型1的点对，则其对Schultz指标的贡献值为 vi,vj V()Gd()G()vi,vj()d()G()vi+d()G()vj =dG()vi,vj=1vivj E()Gd()G()vi,vj()d()G()vi+d()G()vj+dG()vi,vj 1vivj E()Gd()G()vi,vj()d()G()vi+d()G()vj =dG()vi,vj=1vivj E()G22n-2dG()vi+2n-2dG()vj+dG()vi,vj 1vivj E()G2n-2dG()vi+2n-2dG()vj =vivj E()G2()4n-2()dG()vi+dG()vj+vivj E()G()4n-2()dG()vi+dG()vj =2n3-2n2+4m-2M1()G（2）若u和v是类型2的点对，则其对Schultz指标的贡献值为 xi,xj v()Xd()G()xi,xj()d()G()xi+d()G()xj =xi,xj v()X2n-1-dG()vi+2n-1-dG()vj12冯 旭，等：关于Mycielski图补图的一些指标的结果 =xi,xj v()X2()2n-1-()dG()vi+dG()vj =2n3-3n2+(1-2m)n+2m（3）若u和v是类型3的点对，则其对Schultz指标的贡献值为当i=j时，有vi v()G,xj v()xd()G()vi,xj()d()G()vi+d()G()xj=vi v()G 1()2n-2dG()vi+2n-1-dG()vi=4n2-n-6m当 i j 时，有 vi v()G,xj v()Xd()G()vi,xj()d()G()vi+d()G()xj =vivj E()Gvi V()G,xj V()X2()4n-1-()dG()vi+dG()vj-dG()vi（1）+vivj E()Gvi V()G,xj V()X()4n-1-()dG()vi+dG()vj-dG()vi（2）其中，式()1为4m()4n-1-2vivj E()Gvi V()G,xj V()X()dG()vi+dG()vj-2vivj E()Gvi V()G,xj V()XdG()vi=16mn-4m-6M1()G式()2为2()4n-1()C2n-m-vivj E()Gvi V()G,xj V()X()dG()vi+dG()vj-vivj E()Gvi V()G,xj V()XdG()vi=4n3-5n2+(2m+1)n+4m-3M1()G（4）若u和v是类型4的点对，则其对Schultz 指标的贡献值为vi V()G,z Zd()G()vi,Z()d()G()vi+d()G()Z=vi V()G,z Z1()2n-2dG()vi+n=3n2-4m（5）若u和v是类型5的点对，则其对Schultz 指标的贡献值为xi V()X,z Zd()G()xi,Z()d()G()xi+d()G()Z=xi V()G,z Z2()2n-2dG()vi+n =xi V()G,z Z2()3n-2dG()vi =6n2-2n-4m由上述五种情形可得，Mycielski图的补图(G)中的所有点对对Schultz指标的贡献值为S(G)=8n3+3n2-n-4m-5M1(G)定理2 设G是含有n个点和m条边的简单连通图，则其Mycielski图的补图(G)的修正Schultz指标为S*()()G=8n4-4n3+()92-12m n2+()6m-12n+10m2-2m-()10n+52M1()G+8M2()G证明 在(G)中，任意两点u和v分别是以下五种类型的点对：类型1：vi,vj是图G的点，类型2：xi,xj是图G点的拷贝点，类型3：vi,xj是图G的点和图G点的拷贝点，类型4：vi,z是图G的点和根点，类型5：xi,z是图G的拷贝点和根点。（1）若u和v是类型1的点对，则其对修正Schultz指标的贡献值为 vi,vj V()Gd()G()vi,vj()d()G()vid()G()vj =dG()vi,vj=1vivj E()Gd()G()vi,vj()d()G()vid()G()vj+dG()vi,vj 1vivj E()Gd()G()vi,vj()d()G()vid()G()vj13新疆师范大学学报（自然科学版）2024年 =dG()vi,vj=1vivj E()G2(2n-2dG()vi)(2n-2dG(vj)+dG()vi,vj 1vivj E()G(2n-2dG()vi)(2n-2dG(vj)=vivj E()G24n2-4n()dG()vi+dG()vj+4dG()vidG()vj +vivj E()G4n2-4n()dG()vi+dG()vj+4dG()vidG()vj =8mn2-8nM1()G+8M2()G+4n2()C2n-m-4n-M1()G+4-M2()G =2n4-2n3-4mn2+8mn-()4n+2 M1()G+4M2()G（2）若u和v是类型2的点对，则其对修正Schultz指标的贡献值为xi,xj v()Xd()G()xi,xj()d()G()xid()G()xj=xi,xj v()X2n-1-dG()vi2n-1-dG()vj =xi,xj v()X()2n-12-(2n-1)()dG()vi+dG()vj+dG()vidG()vj =2n4-4n3+()52-4m n2+()6m-12n+2m2-2m-12M1()G（3）若u和v是类型3的点对，则其对修正Schultz指标的贡献值为当i=j 时，有vi v()G,xj v()xd()G()vi,xj()d()G()vid()G()xj=vi v()G()2n-2dG()vi()2n-1-dG()vi =vi v()G(4n2-2n)-(6n-2)dG()vi+2dG2()vi =4n3-2n2-12mn+4m+2M1()G当i j 时，有 vi v()G,xj v()Xd()G()vi,xj()d()G()vid()G()xj =vivj E()Gvi V()G,xj V()X2()2n-2dG()vi()2n-1-dG()vi（3）+vivj E()Gvi V()G,xj V()X()2n-2dG()vi()2n-1-dG()vi（4）其中，式（3）为2m()8n2-4n-4nvivj E()Gvi V()G,xj V()XdG()vi+dG()vj+()2-4nvivj E()Gvi V()G,xj V()XdG()vi+4vivj E()Gvi V()G,xj V()XdG()vidG()vj=16mn2-8mn+()2-12n M1()G+8M2()G式（4）为2()4n2-2n()C2n-m-2nvivj E()Gvi V()G,xj V()XdG()vi+dG()vj+()2-2nvivj E()Gvi V()G,xj V()XdG()vi+2vivj E()Gvi V()G,xj V()XdG()vidG()vj=4n4-6n3+()2-20m n2+20mn+8m2-4m+()6n-4 M1()G-4M2()G（4）若u和v是类型4的点对，则其对修正Schultz指标的贡献值为vi V()G,z Zd()G()vi,Z()d()G()vid()G()Z=vi V()G,z Z1()2n-2dG()vin=4n2-4mn（5）若u和v是类型5的点对，则其对修正Schultz 指标的贡献值为xi V()X,z Zd()G()xi,Z()d()G()xid()G()Z=xi V()G,z Z2()2n-1-2dG()vin=4n3-2n2-4mn由上述五种情形可得，Mycielski图的补图(G)的所有点对对修正Schultz指标的贡献值为14冯 旭，等：关于Mycielski图补图的一些指标的结果S*()()G=8n4-4n3+()92-12m n2+()6m-12n+10m2-2m-()10n+52M1()G+8M2()G下面将给出几类特殊图的Mycielski图的补图的Schultz指标和修正Schultz指标。推论1（i）S()(Kn)=3n3+11n2-4n,(n 2);（ii）S()(Ks,t)=8s3+(19t+3)s2+(19t2+2t-1)s+(8t3+3t2-t)，(s,t 1);（iii）S()(Pn)=8n3+3n2-25n+34,(n 3);（iv）S()(Sn)=8n3-2n2+4,(n 2);（v）S()(Cn)=8n3+3n2-25n,(n 3).推论2（i）S*()(Kn)=-32n4+112n3+10n2-6n (n 2)；（ii）S*()(Ks,t)=8s4+()10t-4 s3+(22t2-172t+92)s2+(10t3-172t2+7t-12)s+(8t4-4t3+92t2 -12t),（s,t 1）；（iii）S*()(Pn)=8n4-16n3-152n2+1072n-37,(n 3);（iv）S*()(Sn)=8n4-26n3+48n2-42n+20,(n 2);（v）S*()(Cn)=8n4-16n3-392n2+392n,(n 3).2.2 Mycielski图及其补图的Lanzhou指标命题210（i）Lz()Kn=Lz()-Kn=0;（ii）Lz()Ks,t=st(2st-s-t);（iii）Lz()Pn=2(n-2)(2n-5);（iv）Lz()Sn=(n-1)(n-2);（v）Lz()Cn=4n()n-3.根据以上命题，本节将给出几类特殊图的Mycielski图及其补图的Lanzhou指标。定理3（i）Lz()(Kn)=n4+9n3-16n2+8n,(n 2);（ii）Lz()(Ks,t)=()t+1 s3+(20t2+8t+2)s2+(t3+8t2-2t-1)s+()t3+2t2-t,(s,t 1);（iii）Lz()(Pn)=n3+50n2-159n+150,(n 2);（iv）Lz()(Sn)=2n3+24n2-48n+24,(n 2);（v）Lz()(Cn)=n3+50n2-91n,(n 3).定理4（i）Lz()(Kn)=n4+n3+8n2-8n,(n 2);（ii）Lz()(Ks,t)=()13t+5 s3+(9t2+t-4)s2+(13t3+2t2-2t+1)s+()5t3-4t2+t,(s,t 1);（iii）Lz()(Pn)=29n3-124n2+227n-150,(n 2);（iv）Lz()(Sn)=18n3-48n2+56n-24,(n 2);（v）Lz()(Cn)=29n3-100n2+91n,(n 3).参考文献：1 HAO J X.Theorems about Zagreb Indices and Modified Zagreb Indices J.MATCH Commun.Math.Comput.Chem，2011，65：659-670.2 RANJINI P S，LOKESHA V，CANGL I N，et al.On the Zagreb Indices of the Line Graphs of the Subdivision Graphs J.Appl.Math.Computation，2011，218：699-702.3 DOLI T.Vertex-weighted Wiener Polynomials for Composite Graphs J.Ars Math.Contemp，2008，（01）：66-80.4 RANJINI P S，LOKESHA V，BINDUSREE M，et al.New Bounds on Zagreb Indices and Zagreb Coindices J.Bol.Soc.Paran.Mat，15新疆师范大学学报（自然科学版）2024年2012，（31）：51-55.5 HUA H B，ASHRAFI A R，ZHANG L B.More on Zagreb Coindices of Graphs J.Faculty of Sci and Math，2012，6：1210-1220.6 ASHRAFIA R，DOLI T，HAMZEH A.The Zagreb Coindices of Graph Operations J.Discrete Appl.Math，2010，158：1571-1578.7 MATEJI M，MILOVANOVI E，MILOVANOVI I，et al.A Note on the First Zagreb Index and Coindex of Graphs J.Commun.Comb.Opti，2021，（06）：41-51.8 MILOVANOVI E，MILOVANOVI I.Sharp Bounds for the First Zagreb Index and First Zagreb Coindex J.Miskolc Math Notes，2015，16（02）：1017-1024.9 GUTMAN I.Degree-based Topological Indices J.Croat Chem Acta，2013，86（04）：351-361.10 VUKICEVIC D，LI Q，SEDLAR J，et al.Lanzhou Index J.MATCH Commun.Math.Comput.Chem，2018，80（03）：863-876.11 DEHGARDI N，LIU J.Lanzhou Index of Trees with Fixed Maximum Degree J.MATCH Commun.Math.Comput.Chem，2021，（86）：3-10.12 FURTULA B，GUTMAN I.A Forgotten Topological Index J.J Math Chem，2015，53（04）：1184-1190.13 LIU J B，MATEJI M，MILOVANOVI E，et al.Some New Inequalities for the Forgotten Topological Index and Coindex of Graphs J.MATCH Commun.Math.Comput.Chem，2020，（84）：719-738.14 马丽，孙丹丹.Mycielski图的拓扑指数的相关结果（英文）J.曲阜师范大学学报（自然科学版），2020，46（04）：63-68.15 RUDNICKI P，STEWART L.The Mycielskian of a Graph J.Formalized Math，2011，（19）：27-34.Results on Some Indices of Complements of Mycielski GraphsFENG Xu，MA Li*，FENG Na，WANG Ya-hui，RESALAITI Muhaimaiti（College of Mathematics and Physics，Xinjiang Agricultural University，Urumqi，Xinjiang，830052，China）Abstract：Topology index is a mathematical descriptor of molecular structure,which digitizes the structural characteristics of molecules such as shape,size,and branching.It is easy to calculate,has objective values,and is not easily limited by experience and experiments.The study of topological index graph invariants is currently one of the most active research areas in chemical graph theory,which can be used to describe and predict the physicochemical or pharmacological properties of organic compounds.This article studies two types of degree distance metrics for the complement of Mycielski graphs:Schultz index and modified Schultz index.At the same time,expressions for the Lanzhou index of Mycielski graphs and their complement graphs of some special graphs are also provided.Keywords：Mycielski Graph；Schultz index；Modified Schultz index；Lanzhou index16