树和单圈图的带和权Mostar指标_甄倩倩.pdf

第 42 卷第 3 期2023 年 6 月兰州交通大学学报Journal of Lanzhou Jiaotong UniversityVol 42 No 3Jun 2023收稿日期:2022-12-21学报网址:https:/lztx cbpt cnki net作者简介:甄倩倩(1999 )，女，甘肃镇原人，硕士研究生，主要研究方向为代数图论及其应用。E-mail:zhenqianq1029163 com文章编号:1001-4373(2023)03-0139-05DOI:10 3969/j issn 1001-4373 2023 03 019树和单圈图的带和权 Mostar 指标甄倩倩(兰州交通大学 应用数学研究所，兰州730070)摘要:不包含圈的简单连通图称为树，顶点数和边数相同的简单连通图称为单圈图。在 Mostar 指标的基础上，为求得树和单圈图的带和权 Mostar 指标的上下界，根据割边的特殊性，通过计算发现将图的非平凡割边变为悬挂边，其带和权 Mostar 指标变大，在此基础上，对两类图的结构进行分析，对树进行移边变换，对单圈图进行缩圈变换，最终确立了树和单圈图的带和权 Mostar 指标的上下界并刻画了达到相应界值的极值图，同时给出了圈长固定时，单圈图的带和权 Mostar 指标的上界和其达到上界的极值图。关键词:带和权 Mostar 指标;树;单圈图中图分类号:O157 5文献标志码:ASum-weighted Mostar Index of Trees and Unicyclic GraphsZHEN Qian-qian(School of Mathematics and Science，Lanzhou Jiaotong University，Lanzhou 730070，China)Abstract:A graph without cycles is called tree if is connected，while a graph is called unicyclic graphs ifit is connected and has the same number of vertices and edges Based on the Mostar index，to obtain theupper and lower bounds of the sum-weighted Mostar index of trees and unicyclic graphs，according to theparticularity of the cut edge，it is found through calculation that the non-trivial cut edge of the graph ischanged into pendant edge，and the sum-weighted Mostar index becomes larger On this basis，by analy-zing the structure of these two kinds of graphs，the edge-shifting transformation is performed on the tree，and the cycle-shrinking transformation is performed on the unicyclic graph，the upper and lower bounds ofthe sum-weighted Mostar index of trees and unicyclic graphs are established and the extremal graphs reac-hing the corresponding bounds are characterized At the same time，the upper bound of the sum-weightedMostar index of the unicyclic graphs and the extreme value graph reaching the upper bound are givenwhen the circle length is fixedKey words:sum-weighted Mostar index;trees;unicyclic graphs图的拓扑指标是化学图论中的一个重要部分，也是研究的主要内容之一。研究最早也最广泛的拓扑指标是 Wiener 指标，它是由化学家 Wiener 在1947 年提出的1，1994 年，Gutman 在 Wiener 指标的基础上进行推广，得到了 Szeged 指标2，文献 3-4 提出了加权 Szeged 指标。键加性指标是指图的所有边贡献之和的一类指标，因此，Wiener 指标、Szeged 指标和加权 Szeged 指标都属于键加性指标。2018 年 Dolic等5 引入了一个新的键加性指标，即Mostar 指标，同时计算出了树和单圈图的上下界并刻画了其达到上下界的极值图，然后用一种切割方法6 计算了几类化学图的 Mostar 指标。Mostar 指标兰州交通大学学报第 42 卷自提出这几年，很多专家学者对其进行了大量的研究，请参考文献 7-11。2020 年，Arockiaraj 等12 提出了带和权 Mostar 指标和带积权 Mostar 指标，并计算了石墨烯、石墨炔和石墨炔的带和权 Mostar 指标。Kandan 等13 计算了锥齿轮图和广义齿轮图的带和权 Mostar 指标和带积权 Mostar 指标。Imran等14 研究了 3 种树状聚合物，即酞菁、三嗪和纳米分子图的带和权 Mostar 指标。本文接下来介绍了相关图的术语及其符号，给出了 Mostar 指标和带和权 Mostar 指标的定义式，并通过两个引理和一个图形变换得出了树的上下界及其极值图，给出了固定圈长时单圈图的带和权 Mo-star 指标的上界，以及不考虑圈长时的单圈图的带和权 Mostar 指标的上下界，同时确定了极值图。带和权 Mostar 指标自提出这几年来，在化学图、树状大分子图中研究较多，本文基于树和单圈图 Mostar指标上下界的分析，考虑度和对整个指标的影响，最终给出树和单圈图的带和权 Mostar 指标的上下界并刻画了其到达上下界的极值图。1定义及预备知识本文中所有图都是无向有限的简单图。给定一个图 G，V(G)是其顶点集，E(G)是其边集，顶点 u的度是指与其关联的顶点的数目，用dG(u)表示，度为1的点称为叶子。设e=uv是G中的一条边，nu(e)指集合Nu(e)=xV(G)d(x，u)d(x，v)中元素的个数，n0(e)指集合 N0(e)=x V(G)d(x，u)=d(x，v)中元素的个数，在不考虑图干扰的情况下，有时候也简单记为 nu和 n0。分别用 Sn，Pn和 Cn表示 n 个点的星图、路图和圈图。非悬挂边的割边称为非平凡割边。文章中提及的其他术语和符号请参考文献 15。图 G 的 Mostar 指标定义为 Mo(G)=e=uvE(G)|nu(e)nv(e)|，带和权 Mostar 指标定义为 w+Mo(G)=e=uvE(G)(dG(u)+dG(v)|nu(e)nv(e)|。为了方便起见，我们用G(e)=|nu(e)nv(e)|定义边 e 对图 G 的 Mostar 指标的贡献，G(e)=(dG(u)+dG(v)|nu(e)nv(e)|定义边 e 对图 G的带和权 Mostar 指标的贡献，在不考虑图干扰的情况下，也分别简记为(e)和(e)。2树本节中我们确定了给定顶点数的树的带和权Mostar 指标的上下界和相应的极值图。以下引理是本篇文章的关键。引理2 1设 G 是一个 n 阶连通图，e 是 G 中的一条边，则(e)n 2，等号成立当且仅当 e 是悬挂边。证明设e=uv，我们知道nu1，nv1且nu+nv+n0=n，则(e)=|nu nv|=|n n0 2nv|n 2，等号成立当且仅当 n0=0，nv=1，即e是悬挂边。引理2 2设 G 是一个连通图，e 是图 G 的一条非平凡割边，令 G 是将 e 收缩于一点 u，并添加与 u相连的叶子点 v 得到的图，如图 1 所示。则:w+Mo(G)w+Mo(G)。图 1割边变换Fig 1Cut edge conversion证明显然 dG(u)=dG(u)+dG(v)1，dG(v)=1，那么dG(u)+dG(v)=dG(u)+dG(v)，又由引理2 1 得，变换后 G(uv)G(uv)，所以边e=uv 对带和权 Mostar 指标的贡献变大。而 G 中与u(或v)相关联的所有边(e=uv除外)，变换后度和都变大，但 G(e)=G(e)，所以这些边对带和权Mostar 指标的贡献也变大。其余边对带和权 Mostar指标的贡献保持不变。因此w+Mo(G)w+Mo(G)。定理 2 1设 Tn是 n 个顶点的树，则w+Mo(Pn)w+Mo(Tn)w+Mo(Sn)(1)左边等式成立当且仅当 TnPn，右边等式成立当且仅当 Tn Sn。证明由引理 22，很容易得到树的带和权Mostar指标达到上界的图是星图。上界为w+Mo(Sn)=n(n 1)(n 2)=n3 3n2+2n。当 n3 时，下界显然成立，因此，不妨假设n4。设Tn是n个顶点的树(n4 且TnPn)，则Tn中存在一个度至少为3 的点，记为t，且Tn t 至少有两个连通分支是路，这两条路分别记为Pk=u1u2uk，Pl=v1v2vl，其中:1 k l。为了方便起见，我们记dTn(t)=a(a 3)。令 Tn=Tn uk1uk+vluk，如图2 所示。当 k=1 时，uk1=t。需证，w+Mo(Tn)w+Mo(Tn)。分以下两种情况:情况1当k 2 时，上述变换只影响了 uk1和041第 3 期甄倩倩:树和单圈图的带和权 Mostar 指标vl的度。且注意到除了两条路上的边对带和权 Mostar指标的贡献发生了变化之外，其余边对带和权 Mostar指标的贡献都保持不变。因此，w+Mo(Tn)w+Mo(Tn)=(a+2)|n 2k|+4|n 2(k 1)|+3|n 2|+(a+2)|n 2l|+4|n 2(l 1)|+3|n 2|(a+2)|n 2(k 1)|4|n 2(k 2)|3|n 2|(a+2)|n 2(l+1)|4|n 2l|3|n 2|=(a+2)|n 2k|+4|n 2(k 1)|(a+2)|n 2(k 1)|+(a+2)|n 2l|4|n 2l|(a+2)|n 2(l+1)|=(a+2)|n 2k|+(2 a)|n 2(k 1)|+(a 2)|n 2l|(a+2)|n 2(l+1)|。图 2移边变换Fig 2Edge-shifting transformation因为 nk+l+a 1，等式成立当且仅当与点 t关联的边除了边 tu1和 tv1外，其余关联边为悬挂边，则:1)n2l+2，有:(a+2)|n 2k|+(2 a)|n 2(k 1)|+(a 2)|n 2l|(a+2)|n 2(l+1)|=(n 2k)(a+2+2 a)+2(2 a)+(n 2l)(a 2 a 2)+2(a+2)=4(n 2k)+4 2a 4(n 2l)+2a+4=8(l k+1)0;2)n2l，有:(a+2)|n 2k|+(2a)|n 2(k 1)|+(a 2)|n 2l|(a+2)|n 2(l+1)|=(n 2k)(a+2+2 a)+2(2 a)+(a 2)(2l n)(a+2)(2+2l n)=4(n 2k)+4 2a+(2l n)(a 2 a 2)2(a+2)=8n 8k 8l 4a=4(2n 2k 2l a)0;3)n=2l+1，有:(a+2)|n 2k|+(2 a)|n 2(k 1)|+(a 2)|n 2l|(a+2)|n 2(l+1)|=(n 2k)(a+2+2 a)+2(2 a)+(a 2)(a+2)=4(n 2k)+4 2a+a 2 a 2=4n 8k 2a 0。情况2当k=1 时，变换后除了两条路上的边和与 t 相关联的边外，其余边对带和权 Mostar 指标的贡献保持不变。由于 dTn(t)=dTn(t)1，则除了两条路上的边 tu1和 tv1外，其余关联边由于度和减小，而 Tn(e)=Tn(e)，所以 Tn(e)Tn(e)。下面考虑两条路上的边对带和权 Mostar 指标的贡献。w+Mo(Tn)w+Mo(Tn)=(a+1)|n 2|+(a+2)|n 2l|+3|n 2|(a+1)|n 2(l+1)|4|n 2l|3|n 2|=(a+1)|n 2|+(a+2)|n 2l|4|4 2l|(a+1)|n 2l 2|=(a+1)|n 2|+(a 2)|n 2l|(a+1)|n 2l 2|=(a+1)(|n 2|n 2l 2|)+(a 2)|n 2l|0。则上述变换严格降低了树的带和权 Mostar 指标的值，重复变换，就得到了路图。通过计算，当 n 0(mod2)时，w+Mo(Pn)=2n2 6n+4，当 n 0(mod1)时，w+Mo(Pn)=2n2 6n+6。3单圈图本节中，我们给出了固定圈长的单圈图的带和权 Mostar 指标的上界以及对应的极值图，在此基础上，通过缩圈变换给出了不考虑圈数时的单圈图的带和权 Mostar 指标的上下界，同时刻画了相对应的极值图。设 Sn，k表示圈长为 k 的n 个顶点的单圈图，其中n k 个不在唯一圈上的顶点作为叶子都与圈 Ck的一个固定顶点相邻，圈 Ck除那个固定顶点外的其余顶点在 Sn，k中的度均为 2(见图 3)。定理3 1设Un，k是圈长为k的n(n3)个顶点的单圈图，则w+Mo(Un，k)w+Mo(Sn，k)(2)等式成立当且仅当 Un，k Sn，k。证明通过引理22 的变换过程，我们得到了一个比 Un，k具有更大带和权 Mostar 指标的图 Un，k，其中:Un，k是n k 个点都以叶子的形式附着在k 圈的各个顶点上的单圈图。设Un，k的圈Ck=v1v2vkv1，令ci是点vi所连接的叶子数。现在考虑 k 的奇偶性两种情况。情况 1k 为偶数，设 k=2t，对任意 i，有:(vivi+1)=(4+ci+ci+1)|ci+1+ci+2+ci+t141兰州交通大学学报第 42 卷ci+t+1 ci+t+2 ci|(4+ci+ci+1)(n k)。注意到如果 n k 个叶子全部都悬挂在 vi+1，vi+2，vi+t，或者vi+t+1，vi+t+2，vi上，则上述式子达到最大值(4+ci+ci+1)(n k)。对(vivi+1)求和:ki(vivi+1)(4+c1+c2)(n k)+(4+c2+c3)(n k)+(4+ck+c1)(n k)=(n k)(4+c1+c2+4+c2+c3+4+ck+c1)=(n k)(2n+2k)=2n2 2k2。很容易看出，为了确保上述式子的等式成立，则必须保证 n k 个叶子都悬挂在 k 圈的同一个顶点上。此时圈上的边对带和权 Mostar 指标的贡献达到最大值:2n2 2k2。图 3图 Sn，kFig 3Graph of Sn，k我们发现对于n k个悬挂边来说，(e)固定，当其都悬挂在圈上的同一个顶点上时，每个悬挂边的度和达到最大。此时，单圈图 Sn，k的带和权 Mostar指标达到最大值:w+Mo(Sn，k)=2n2 2k2+(n k)(3+n k)(n 2)=2n2 2k2+(3n+n2 2nk 3k+k2)(n 2)=n3+(3 2k)n2+(k2+k 6)n 4k2+6k。情况 2k 为奇数，设 k=2t+1，对任意 i，有:(vivi+1)=(4+ci+ci+1)|ci+1+ci+2+ci+tci+t+2 ci+t+3 ci|(4+ci+ci+1)(n k ci+t+1)。注意到如果 n k 个叶子全都悬挂在 vi+1，vi+2，vi+t，vi+t+1，或者vi+t+1，vi+t+2，vi上，则上述式子达到最大值(4+ci+ci+1)(n k ci+t+1)。对(vivi+1)求和:ki(vivi+1)(4+c1+c2)(n k c2+t)+(4+c2+c3)(n k c3+t)+(4+ck+c1)(n k c1+t)=(4+c1+c2)(n k)+(4+c2+c3)(n k)+(4+ck+c1)(n k)4(c2+t+c3+t+c1+t)(c1+c2)c2+t(c2+c3)c3+t (ck+c1)c1+t=(n k)(2n+2k)4(n k)(c1+c2)c2+t(c2+c3)c3+t(ck+c1)c1+t(n k)(2n+2k)4(n k)。要使上述等式成立，当且仅当对每个 i 都有(vivi+1)=(4+ci+ci+1)(n k ci+t+1)，即 n k个叶子全部悬挂在圈上的同一个顶点上，此时(c1+c2)c2+t=(c2+c3)c3+t=(ck+c1)c1+t=0，则圈上的边对带和权 Mostar 指标达到最大贡献:(n k)(2n+2k)4(n k)。同理，对于n k个悬挂边来说，(e)固定，且当其都悬挂在圈上的同一个顶点上时，每个悬挂边的度和达到最大，此时，单圈图 Sn，k的带和权 Mostar 指标达到最大值:w+Mo(Sn，k)=(n k)(2n+2k)4(n k)+(n k)(3+n k)(n 2)=n3+(3 2k)n2+(k2+k 6)n 4k2+6k 4(n k)=n3+(3 2k)n2+(k2+k 10)n 4k2+10k。定理 3 2设 Un是 n 个顶点的单圈图，则:0 w+Mo(Un)n3 3n2+2n 6(3)左边等式成立当且仅当UnCn，右边等式成立当且仅当 Un Sn，3。证明显然w+Mo(Cn)=0。而对不同于Cn的单圈图 Un，至少有一条悬挂边，这个悬挂边对带和权 Mostar 的贡献大于 0，因此有，w+Mo(Un)w+Mo(Cn)，等式成立当且仅当 Un Cn。接下来考虑上界。设 Un是 n 个顶点的单圈图，不妨设 Un的圈长为 k，由定理 3 1 知，Sn，k是达到最大带和权Mostar指标的圈长为k的单圈图，对Sn，k进行缩圈变换(见图 4):记圈上度大于 2 的点为 w，将圈上与 w 相关联的任意一条边收缩于 w 点，并在该点悬挂一个叶子，记为 Sn，k1，则证 w+Mo(Sn，k)w+Mo(Sn，k1)。当 k 为偶数时，w+Mo(Sn，k)=n3+(n 4)k2+(3 2k)n2+nk+6k 6n，缩圈后变奇圈，w+Mo(Sn，k1)=n3+(n 4)(k 1)2+(3 2(k 1)n2+n(k 1)+10(k 1)10n。w+Mo(Sn，k1)w+Mo(Sn，k)=n3+(n 4)(k 1)2+(3 2(k 1)n2+n(k 1)+10(k 1)10n (n3+(n 4)k2+(3 2k)n2+nk+6k 6n)=2n22nk 4n+12k 14=(2n 4)(n k)+8k 14 0。当 k 为奇数时，w+Mo(Sn，k)=n3+(n 4)k2+(3 2k)n2+nk+10k 10n，缩圈后变偶圈，此时w+Mo(Sn，k1)=n3+(n 4)(k 1)2+(3 2(k 241第 3 期甄倩倩:树和单圈图的带和权 Mostar 指标1)n2+n(k 1)+6(k 1)6n。w+Mo(Sn，k1)w+Mo(Sn，k)=n3+(n 4)(k 1)2+(3 2(k 1)n2+n(k 1)+6(k 1)6n (n3+(n 4)k2+(3 2k)n2+nk+10k 10n)=2n22nk+4n+4k 10=2n(n k)+4n+4k 10 0。可以看出，缩圈变换使单圈图的带和权 Mostar 指标变大，重复变换直至4圈缩为3圈，此时的单圈图Sn，3达到最大的带和权 Mostar 指标:w+Mo(Sn，3)=n33n2+2n 6。图 4缩圈变换Fig 4Cycle-shrinking transformation4结论1)设 Tn是 n 个顶点的树，当 Tn Sn时，树达到最大带和权Mostar指标，其最大值为n33n2+2n;当 Tn Pn时，树达到最小带和权 Mostar 指标，n 为偶数时，其最小值为 2n2 6n+4;n 为奇数时，其最小值为 2n2 6n+6。2)设 Un是 n 个顶点的单圈图，当 Un Cn时，单圈图达到最小带和权 Mostar 指标，其值为 0;当UnSn，3时，单圈图达到最大带和权Mostar指标，其最大值为 n3 3n2+2n 6。目前国内外对简单连通图的带和权 Mostar 指标的研究还不是很多，本文的一些简单连通图的Mostar 指标的加权版本具有很好的参考意义，特别是树和单圈图的带积权 Mostar 指标。参考文献:1WIENE H Structural determination of paraffin boilingpointsJ Journal of the American Chemical Society，1947，69(1):17-20 2 GUTMAN I A formula for the Wiener number of trees andits extension to graphs containing cycles J Graph Theo-ry Notes NY，1994，27(9):9-15 3 ILICA，MILOSAVLJEVICN The weighted vertex PI in-dex J Mathematical and Computer Modelling，2013，57(3/4):623-631 4NAGAAJAN S，PATTABIAMAN K，CHANDASEKHA-AN M Weighted Szeged index of generalized hierarchicalproduct of graphs J General Mathematics Notes，2014，23(2):85-95 5 DOLICT，MATINJAK I，KEKOVSKI，et al Mo-star indexJ Journal of Mathematical Chemistry，2018，56:2995-3013 6 KLAVZA S，GUTMAN I，MOHA B Labeling of benze-noid systems which reflects the vertex-distance relations J Journal of Chemical Information and Computer Sci-ences，1995，35(3):590-593 7 DEHGADI N，AZAI M More on Mostar index J Ap-plied Mathematics E-notes，2020，20:316-322 8 GAO F，XU K X，DOLICT On the difference of Mostarindex and irregularity of graphs J Bulletin of the Malay-sian Mathematical Sciences Society，2021，44(2):905-926 9 GHOBANI M，AHMANI S，ESLAMPOO M Some newresults on Mostar index of graphsJ Iranian Journal ofMathematical Chemistry，2020，11(1):33-42 10 DENG K C，LI S C Chemical trees with extremal MostarindexJ Match Communications in Mathematical andin Computer Chemistry，2021，85:161-180 11 DENG K C，LI S C On the extremal values for the Mo-star index of trees with given degree sequenceJ Ap-plied Mathematics and Computation，2021，390:125598 12 AOCKIAAJ M，CLEMENT J，TATNIK N，et al Weigh-ted Mostar indices as measures of molecular peripheralshapes with applications to graphene，graphyne and graph-diyne nanoribbons J SA and QSA in Environmentalesearch，2020，31(3):187-208 13 KANDAN P，SUBAMANIAN S，AJESH P Weighted Mo-star indices of certain graphs J Advances in Mathemat-ics，2021，10:3093-3111 14 IMAN M，AKHTE S，YASMEEN F，et al The weigh-ted Mostar invariants of Phthalocyanines，triazine-basedand nanostar dendrimersJ Polycyclic Aromatic Com-pounds，2023，43(1):772-789 15 BONDY J A，MUTY U S Graph theory with applica-tions M London:Macmillan，1976(责任编辑:赵冬艳)341