单圈图的Steiner Wiener指数的极值问题.pdf

Sep.,2023OperationsResearchTransactionsVol.27No.32023年9 月第2 7 卷第3 期运筹学学报DOI:10.15960/ki.issn.1007-6093.2023.03.015单圈图的SteinerWiener指数的极值问题张杰1t姬燕2摘要Wiener指数作为化学图论中的一个重要的化学指标，是连通图的任意两个顶点的距离之和。SteinerWiener指数是Wiener指数的一种推广形式，定义为所有k个顶点的集合S的Steiner距离的和，其中S的Steiner距离是包含S的最小连通子图的边数。本文研究了具有最小（大）SteinerWiener指数的单圈图结构。关键词SteinerWiener指数，Steiner距离，单圈图，Wiener指数中图分类号O157.52010数学分类号号0 5C05,05C12Extremal problems for Steiner Wienerindex of unicyclic graphsZHANG Jiel,tJI Yan?Abstract Wiener index is an important chemical index in chemical graph theory,defined as the sum of distances between all pairs of vertices.A generalization of theWiener index,called the Steiner Wiener index,takes the sum of the Steiner distancesover all sets S of cardinality k.The Steiner distance of vertices in a set S is the minimumsize of a connected subgraph that contain these vertices.We consider the extremalproblems with respect to the Steiner Wiener index among all unicyclic graphs.Keywords Steiner Wiener index,Steiner distance,unicyclic graphs,Wiener indexChinese Library Classification O157.52010 Mathematics Subject Classification 05C05,05C12令G为简单图，其顶点集为V(G),边集为E(G)。图G是由G通过删去顶点U和与邻接的所有的边得到的图。树是一类满足|E(G)|=V(G)|1的连通图，单圈图是一类满足|E(G)|=|V(G)I的连通图，n个顶点的星图记为Sn，n 个顶点的路记为Pn。本文中其它的图论中的定义和符号参见文献 1。Wiener指数作为化学图论中的重要指标，由Wiener在19 47 年引入，该指数被认为与化学分子的沸点密切相关。Wiener指数作为图的最常见的不变量之一，定义为图中所收稿日期：2 0 19-0 9-18*基金项目：国家自然科学基金（Nos.1170137211801371)，上海市自然科学基金（No.16ZR1422400)，上海市“人才发展资金”（No.2018071)，上海市“扬帆计划”（No.19YF1435500)1.上海立信会计金融学院，上海2 0 12 0 9;Shanghai Lixin University of Accounting and Finance,Shang-hai 201209,China2.山东省平阴县实验学校，山东济南2 50 40 0;Pingyin Experimental School，Ji n a n 2 50 40 0，Sh a n d o n g，China十通信作者E-mail:1793期单圈图的SteinerWiener指数的极值问题有顶点对的距离的和（见文献 2，最初的表达式是：W(G)=dist(u,),u,vEV(G)其中dist(u,)是图G中两个顶点u和之间的距离，即顶点u到的最短路径所含的边的数目。对于图的顶点集V(G)的子集SV(G)，S的Steiner距离d(S）是图G的包含顶点集S的最小连通子图所含的边数。当IS|=2时，d(S）恰好是两个顶点之间的距离。很自然的从这个角度出发可以把Wiener指数推广到SteinerWiener指数，SteinerWiener指数定义为 3:SWk(G)=d(S)。SCV(G),ISI=k在上世纪9 0 年代，Steiner平均距离已经在文献 4,5中进行了研究，Steiner平均距离与SteinerWiener指数只差一个常数倍。最近，SteinerWiener指数作为一类化学指数在很多文章中进行了研究 3,6-15。在文献 3 中，刻画了树的集合中最大化和最小化SteinerWiener指数的极值树。在文献 9 中，给出了在固定直径的树的集合中最小化SteienrWiener指数的极值树。SteinerWiener指数在k=2时的值恰好是Wiener指数，关于Wiener 指数的研究更是有大量的结果 16-2 1,于桂海和冯立华在文献 19 中探讨了给定圈长的单圈图的集合中最大化和最小化Wiener指数的极值图。本文我们将研究给定圈长的单圈图的集合中关于SteinerWiener指数的极值图的结构。我们先给出几个定义：令Un是n个顶点的单圈图的集合，Un,g是n个顶点的、圈长为g的单圈图的集合。GEUn,g，则G记为G(Tu1，,Tu。)，圈记为Cg，圈上的点分别记为U1,U2，U g，T 是把G中圈上的边删掉后包含顶点；的子树，简记T。G=G(Sn-9+1)Eun.g，它是把星图 Sn-g+1的中心点和圈C。上的一个点黏在一起得到的图。我们的主要结果是：定理1在集合Un，中，我们有：(1)G*是具有最小SteinerWiener指数的极值图。(2)若Tu1,.,To。白的顶点个数分别为l1,，l g，当l1,，l。保持不变时，G(Pi，P）是具有极大SteinerWiener指数的极值图，其中Pi，P。是以圈上的顶点u1,，u g 为端点，顶点个数为l1,，l。的路（1ln-g+1,1ig)。推论1在集合Un中，G(Sn-2）是具有最小SteinerWiener指数的极值图，其值为SWa(G(Sn-2)=()*k+(*=1)*(k-1).一1Steiner Wiener 指数的性质令SWk+1(G,u）是V(G)所有含有u的k+1元子集S的Steiner距离的和。引理令EV(G),记H和 H是G的两个连通子图，且V(Hi)nV(H2)=u)。见图1。则k-1IV(H2)|-1)SWk(G)=SWk(Hi)+SWh(H2)+SWi+1(H1,u)k-j3=118027卷张杰，姬燕k-1k-2(IV(H1)|-1)SWe-+(H2,u)+2(IV(H2)I-1)SWi+1(H1,u)k-1-jj=1j=1k-2(IV(H1)/-1)SWk-j(H2,u)。=1HH2图1引理1中的图G证明按照顶点集S位于V(G）中的哪个子集合，我们分以下三种情形讨论来计算SWk(G)的值:情形 1 若 S CV(Hi),则 dc(S)=dHi(S)。情形 2 若 S V(H2),则 dc(S)=dH(S)。情形3 若 nV(Hi)(u)0,SnV(H2)(u)0,记 Si=SV(Hi)(u)=SnV(Hi-u),S2=SnV(H2)(u)=SnV(H2-u)。情形3.1uS。记|Sil=j,则|S2l=k-j。故dc(S)SnV(Hi-u)*0,Snv(H2-u)+0,usk-1dc(Si U S2 U(u)j=11S1l=j,IS21=k-j,SiCV(Hi-u),S2CV(H2-u)k-1(dHi(Si U(u)+(dH,(S2 U(u)j=11S1l=j,IS21=k-j,SiCV(Hi-u),S2CV(H2-u)k-1k-1dHi(Si U(u)+ZdHz(S2 U(u)j=11S1l=j,j=1IS1l=j,IS21=k-j,1S21=k-j,SicV(Hi-u),SiCV(Hi-u),S2CV(H2-u)S2CV(H2-u)k一(IV(H2)/-1)k-1)SWi+(H1,u)+2(IV(Hi)/-1)SWk-j+1(H2,u)。k-jj=1j=1情形3.2 uES。记|Si|=j,则S2|=k-1-j。1813期单圈图的SteinerWiener指数的极值问题通过简单的计算，dc(S)SnV(H1)(u)?0,V(S)nV(H2)(u)+0,uEsk-2(dH(Si U(u)+dH,(S2 U(u)j=11S11=j,IS2l=k-1-j,SiCV(Hi-u),S2CV(H2-u)k-2(IV(H2)|-1)k-2)SWj+(Hl,)+2(IV(Hi)/-1)SWk-j(H2,u)。k-1-jj=1j=1把上述几种情形的结果相加，就得到引理中的结论。2集合合Un.g中关于SteinerWiener指数的极值图令H和T是连通图G的两个连通子图，且V(H)nV(T)=u)。令G是把G的子图T变为T得到的图，且V(H)nV(T)=u)。见图2。HTHT图2对G中的子图T做变换得到G根据引理1，我们有SW(G)-SWk(G)k-1(IV(H)/-1)=SWk(T)-SWk(T)+(SWh-j+1(T,u)-SWk-j+1(T,u)j=1k-2(IV(H)I-1)(SWk-j(T,u)-SWk-j(T,u)。1下面我们证明若T是树，则具有极小SteinerWiener指数的极值图一定满足T是星图，具有极大SteinerWiener指数的极值图一定满足T是路。引理令H和 T是连通图的两个连通子图，且T为树,V(H)nV(T)=u),则当T是u为中心点的星图时 SWk(G)最小，当T是u为端点的路时，SWs(G)最大。证明先证明当T是u为中心点的星图时SWi(G）最小。根据上面计算出的SWk(G）-SWk(G）的表达式，只需要SW(T）和SWk-i+1(T,u）同时都取极小值即可。由文献 7 知，在树的集合中，星图的SteinerWiener 指数最小；对于SWk-i+1(T,u)，因为含有k-j+1个顶点的集合 S的Steiner距离d(S）的最小值等于k，而以u为中心的星图恰恰对于T-u中的任意k-i个点，都有d(S)=k-j。18227卷张杰姬燕下面证明当T是u为端点的路时，SWs(G)最大。根据计算出的SWk(G)-SWi(G)的表达式，只需要SW(T）和SWk-i+1(T,u）都取极大值即可。由文献 7 知，在树的集合中，路的Steiner Wiener 指数最大；SWk-i+1(T,u）取极大值时T必为以u为端点的路径，若T不是路径，取以为端点的最长的路径uuup，不妨设 u;(1ip-1)的度至少为3,u除最长路径上的邻点集合为N(ui）u i-1,i+1=【w 1，w t)，令T=T-uiwi-.-uiwt+upwi+.+upwt。见图 3。显然 SWe-j+1(T,u)SWk-j+1(T,u),矛盾。W2WtW2Wt山i山图3对子图T作变换变为T因此，我们有：定理1的证明月VGUn,，令Gi是把G中的圈Cg上所有的悬挂树T,都变为星图SiT:I后得到的图。由引理2 可知,SWs(GI)SW(G)。图G*可以看成是把G1中的叶子点都与圈Cg上的一个顶点相连得到的图，见图4。下证SWs(G*)SWs(Gi)。情形1 对于固定的i,1ig,若 S C V(T)UV(Cg),则 dc*(S)=dci(S)。情形2 对于ij,1ijg,若 SnV(T)V(Cg)且 SnV(T)V(Cg)0,显然,dG(S)dc(S)。并且一定存在某个集合 S,使得 dc(S)0。S/TilSiTi+IT,lSTdS/T9图4变换:G1 G*在集合Un,，中，对于SteinerWiener 指数取得极大值的极值图的证明由引理2 可得。推论1的证明由定理1可知，只需证 SWs(G(Sn-2)3。显然SWk(G(Sn-2)=(=)*h+(=)*(k-1),而 G(Sn-g+1)任选个点集S的d(S）为k-1的个数小于（=1),且存在s，使得 d(S）k。因此,SWk(G(Sn-2)0这个结论说明了在Un,3中具有最大Wiener指数的图是G(Pn-2)。与于桂海、冯华在文献 19 中证明出的结论一致。3结论和展望关于SteinerWiener指数的极值问题已经在很多集合中进行了研究。比如n个顶点的树的集合 3，给定度序列的树的集合 15，给定最大度的树的集合 15,，给定叶子点的树的集合 15，给定最小度的连通图的集合 6，给定直径的树的集合 9，给定Segment 序列的树的集合 13 等。针对给定圈长的单圈图的集合Un,g的关于SteinerWiener指数的极值问题，我们刻画了当SteinerWiener指数取得最小值和极大值时的极值图结构，进一步得到了Un中具有最小SteinerWiener指数的极值图，并求出了当k=2，g=3 时在集合Un,3中具有最大SteinerWiener指数的极值图，对于k,g的值取一般数值的情形此问题18427卷张杰，姬燕有待更深入的研究。在许多集合中关于SteinerWiener指数的极值图的结构与Wiener指数的极值图的结构是一致的，是否可以找到一些集合两者的极值图结构不一致，以及在其它集合中进一步探讨SteinerWiener指数的极值图的结构将是很有意义的。参考文献1 Bondy J A,Murty U S R.Graph Theory with Application M.New York:Macmillan Press,1976.22 Wiener H.Structural determination of paraffin boiling points J.Journal of the AmericanChemical Society,1947,69:17-20.3 Li X L,Mao Y P,Gutman I.The Steiner Wiener index of a graph J.Discussiones Mathemat-icae Graph Theory,2016,36:455-465.4 Dankelmann P,Oellermann O R,Swart H C.The average Steiner distance of a graph J.Journal of Graph Theory,1996,22(1):15-22.5 Dankelmann P,Swart H C,Oellermann O R.On the average Steiner distance of graphs withprescribed properties J.Discrete Applied Mathematics,1997,79:91-103.6 Dankelmann P.The Steiner k-Wiener index of graphs with given minimum degree J.DiscreteApplied Mathematics,2019,268:35-43.7 Gutman I.On Steiner degree distance of trees J.Applied Mathematics and Computation,2016,283:163-167.8 Li X L,Mao Y P,Gutman I.Inverse problem on the Steiner Wiener index J.DiscussionesMathematicae Graph Theory,2018,69:83-95.9 Lu L,Huang Q,Hou J,et al.A sharp lower bound on Steiner Wiener index for trees withgiven diameter J.Discrete Mathematics,2018,341:723-731.10 Mao Y P,Wang Z,Gutman I.Steiner Wiener index of graph products J.Transactions onCombinatorics,2016,5(3):39-50.11 Mao Y P,Wang Z,Gutman I,et al.Steiner degree distance J.MATCH Communications inMathematical and in Computer Chemistry,2017,78(1):221-230.12 Mao Y P,Wang Z,Gutman I,et al.Nordhaus-Gaddum-type results for the Steiner Wienerindex of graphs J.Discrete Applied Mathematics,2017,219:167-175.13 Zhang J,Wang H,Zhang X D.The Steiner Wiener index of trees with a given segment sequenceJ.Applied Mathematics and Computation,2019,344:20-29.14 Zhang J,Gentry M,Wang H,et al.On the inverse Steiner Wiener problem J.MATCHCommunications in Mathematical and in Computer Chemistry,2019,82(3):743-754.15 Zhang J,Zhang G J,Wang H,et al.On extremal trees with respect to the Steiner Wienerindex J.Discrete Mathematics Algorithms and Applications,2019,11(6):1950067.16 Fischermann M,Hoffmann A,Rautenbach D,et al.Wiener index versus maximum degree intrees J.Discrete Applied Mathematics,2002,122:127-137.17 Liu H,Pan X F.On the Wiener index of trees with fixed diameter J.MATCH Communicationsin Mathematical and in Computer Chemistry,2008,60:85-94.18 Wang H.The extremal values of the Wiener index of a tree with given degree sequence J.Discrete Applied Mathematics,2008,156:2647-2654.19 Yu G H,Feng L H.On the Wiener index of unicyclic graphs with given girth J.Ars Combi-natoria,2010,94:361-369.20 Zhang J,Wang H,Zhang X D.The Wiener index of trees with given degree sequence andsegment sequence J.MATCH Communications in Mathematical and in Computer Chemistry,2019,81(1):105-118.21 Zhang X D,Xiang Q Y,Xu L Q,et al.The Wiener index of trees with given degree sequencesJ.MATCH Communications in Mathematical and in Computer Chemistry,2008,60:623-644.