仙人掌图的度偏差指数

洪文豪,汤自凯

(湖南师范大学 数学与统计学院,湖南 长沙,410081)

图的拓扑指数是图的不变量,能很好的体现图的性质。它不仅能够实现分子结构信息的数值化,还能够反映出化合物的物理化学性质和生物活性,在化合物的定量结构—性质关系(QSPR)和定量结构—活性关系(QSAR)的研究中具有重要的应用。多个关于图的非正则性拓扑指数被提出,如:1957年由Collatz和Sinogowitz[1]提出了最早的度量图的非正则性的指数;1997年irregularity指数被Albertson[2]提出。2005年Nikforov[3]提出了另一个非正则性拓扑指数—图的度偏差指数:,并证明了一般图关于s(G)与邻接谱的几个不等式。随后对度偏差指数的研究相继展开:Oliveira等[4]给出了图n,p,1PC关于s(G)的极值及其极值图并提出一般图在CS(n,k)处取得极值的猜想;Ghalavand等[5]解决了文献[4]的猜想并计算了一些化学图关于s(G)的值;刘乐乐等[6]研究了k-均匀超图关于s(G)的值;关于度偏差指数的更多研究可见文献[7-9]。而仙人掌图是经常被研究的对象,仙人掌图关于irregularity-指数、ABC-指数、Sombor-指数、Mostar-指数、Randic-指数的极值问题等已经被广泛研究[10-14]。在本文中,仅考虑简单、无向、连通和有限的图。利用分支变换、缩圈变换等图形变换给出了仙人掌图关于度偏差指数的极值以及极值图。

1 预备知识

设图G=(V,E),其中V,E分别表示图的顶点集与边集,令。

dG(vi)表示图G中顶点vi的度(不混淆的情况下可简写为d(vi) ); 序列(d1,d2,…,di,…,dn)表示图G的度序列,其中di=d(vi)且d1≤d2≤…≤dn,nj(1 ≤j≤n-1)表示图G中顶点度为j的个数;N(v)表示顶点v的所有邻点的集合。设C表示一个圈,Ci是第i(1 ≤i≤k)个圈。设P=u0u1...ul(l≥ 1) 是一条路,若满足d(u0)≥ 3,d(ul)= 1 ,d(ui) = 2(1 ≤i≤l-1)则称P为悬挂路;当l=1,d(ul)= 1 时,则称ul为悬挂点,ulu0为悬挂边;若d(u0)≥ 3,d(ul)≥ 3 ,d(ui)=2(1≤i≤l-1),则P称为图G的内部路,Pn表示n个顶点的路。u～v表示顶点u和v相邻。若任意2个圈至多有1个共享顶点的连通图,则称为仙人掌图。设ϑn,k表示有n个顶点,k个圈的仙人掌图,Gn,k∈ϑn,k表示有n个顶点,k个不相交的三角形和n-2k-1条悬挂边共享1个顶点的仙人掌图。记Sn为星图,则Sn+e表示在星图Sn的2个悬挂点之间加1条边e。Sn+e,Gn,k如图1所示。没有提到的定义或术语参见文献[15]。

若图G∈ϑn,k,显然图G有n+k-1条边,则。若1个圈中有且只有1个顶点度大于2,则称为终端圈。为了证明主要结论将使用以下3个简单引理和2个图形变换。

引理1设图G∈ϑn,k,k≥2则。

证明首先由n≥ 2k+1可得2k- 2 ≤n- 3 ,所以。故

命题得证。

由引理1知,s(G)只与n1,n2有关。

1.1 仙人掌图的分支变换

引理2(分支变换) 设图G是含k(k≥ 2 )个圈的仙人掌图,其中有p(2 ≤p≤k)个圈(不一定是终端圈)共点,若存在va∈V(G)是不与共享顶点相同的点。图G＇由图G将p个圈中的某个圈移到顶点va所得。则s(G)-s(G＇)≥ 0。

证明图G到图G＇的分支变换如图2所示。在图G中分d(va)=1,d(va)=2和d(va)≥ 3 3种情况考虑。当d(va)=1时,则图G＇中dG＇(va)＞2,即减少1个一度顶点,由引理1得s(G)-s(G＇)=2(1+(2k-2)/n)＞ 0; 当d(va)=2时,则图G＇中dG＇(va)＞2,即减少1个二度顶点,由引理1得s(G)-s(G＇)=2(2k-2)/n＞0;当d(va)≥ 3时,则图G＇中n1,n2无变化,由引理1得s(G)-s(G＇)=0。综上所述,s(G)-s(G＇)≥ 0。命题得证。

1.2 仙人掌图的缩圈变换

引理3(缩圈变换) 设图G是含k(k≥ 2)个圈的仙人掌图,若图G中存在一个围长大于3的圈C(不一定是终端圈)与一条端点度为3的内部路P共点,设v1是其共享顶点且v1,v2,v3∈V(C),v1～v2,v1～v3。图G＇由图G去掉边v1v3和增加边v2v3所得。则s(G) -s(G') ≤ 0 。

证明图G到图G＇的缩圈变换如图3所示。在图G中分d(v2)＞2和d(v2)=2 2种情况考虑。当d(v2)＞ 2时,则图G＇中dG＇(v1)=2,即增加了1个二度顶点,由引理1可得s(G)-s(G＇)=-2（2k-2)/n＜ 0; 当d(v2)=2时,显然图G＇中n1,n2无变化,由引理1可得s(G)-s(G＇)=0。综上所述,s(G)-s(G＇)≤0。命题得证。

2 仙人掌图的极值

下面先给出树关于度偏差指数的极值及相关极值图。

定理1若G∈ϑn,0,n≥2，即图G是树,则,其中当且仅当G≅Pn时,左边不等式取等;当且仅当G≅Sn时,右边不等式取等。

证明由,有。显然s(G)随着n1增大而增大。又在树中有 2 ≤n≤1n- 1 ,所以n1=2当时,即;当n=n- 1时,即1。定理得证。

下面将给出单圈图关于度偏差指数的极值及相关极值图。

定理2若G∈ϑn,1,n≥3,即图G是单圈图,则0 ≤s(G) ≤ 2n-6,其中当且仅当G≅C时,左边不等式取等;当且仅当G≅Sn+e时,右边不等式取等。

证明由,有。显然s(G)只与n1有关。又因为在单圈图G中有 0 ≤n≤n-3,所1以当n1=0时,即G≅C,s(G)min=0;当n1=n- 3 时,即G≅Sn+e,s(G)max=2n-6。定理得证。

因为当k≥ 2时，顶点个数n≤ 4的仙人掌图不存在。下面将给出k≥ 2,n≥ 5的仙人掌图关于度偏差指数的极大值,并刻画唯一达到极大值的仙人掌图。

定理3若G∈ϑn,k,(k≥2,n≥5),则s(G) ≤ 2n- 6 - (4k-4)/n,当且仅当G≅Gn,k时等号成立。

证明首先由引理1有。其次根据仙人掌图的定义有n1+n2≤n- 1 ,n1≤n-2k-1。因此,只有当n1+n2=n- 1时,才能实现s(G)取最大值。又由引理1可知在s(G)的表达式中n1的系数比n2的系数大,所以当n1=n-2k-1,n2=2k时,即G≅Gn,k,s(G)max=2n-6-(4k-4)/n。定理得证。

下面将给出k≥ 2,n≥ 5的仙人掌图关于度偏差指数的极小值,并刻画能达到极小值的仙人掌图类。

定理4设G∈ϑn,k,(k≥2,n≥5)。

(1)当n/ 3 ＜k≤ (n - 1 )/2时,有s(G) ≥ 2(k+ 2 )(2k-2)/n,当且仅当图G的度序列满足(2,...2,3,...,3,4,...,4)时,等号成立,其中n2=k+ 2 ,n3= 2(n- 2k- 1 ),n4=3k-n;

如图4所示给出了3个特殊的达到极小值的仙人掌图;如图5所示给出了3个特殊的达到极小值的仙人掌图。

证明下面逐步刻画达到极小值的仙人掌图的特点,从而求得极小值。

断言1若图G是关于度偏差指数的极小值图,则图G中不存在悬挂路(点)。

证明(断言1) 假设图G中存在悬挂路。设悬挂路Pi=v1v2. ..viv0,且d(v1)=1,d(v0)≥ 3 。在图G中存在va∈N(v0)且d(va)≥ 2 ,,设G＇由图G去掉边v0va和增加边v1va所得,即G' =G-v0va+v1va,如图6所示。下面分d(v0)=3和d(v0) ＞ 3 2种情况考虑。当d(v0)=3时,图G＇中dG'(v0) =dG'(v1) = 2 ,即增加了2个二度顶点,减少了1个一度顶点,由引理1得;当d(v0) ＞ 3 时,图,即增加了1个二度顶点,减少了1个一度顶点,由引理1得。故与假设矛盾。由此可得极小值图G中不存在悬挂路。同理,也不存在悬挂点。

由断言1知极小值图G中无一度顶点,故s(G)只与n2有关。

断言2若图G是关于度偏差指数的极小值图,则图G中不存在p(p≥ 3 )个圈(这些圈不一定是终端圈)共享1个顶点。

证明(断言2) 假设存在p(p≥ 3 )个圈(这些圈不一定是终端圈)共享1个顶点。由断言1可得图G中所有顶点满足d(v)≥2,再根据引理2的分支变换,把p个圈中的某个圈移到1个二度顶点处,则此时图G＇中减少1个二度顶点,所以s(G)-s(G＇)=2(2k-2)/n＞0。故与假设矛盾。由此可得极小值图G中最多只有2个圈共点。

特别的,当k=(n-1)/2时,可得到唯一的极小值图G且度序列为(2,…,2,4,…,4),其中n2=k+2,n4=k-1。下面考虑k＜(n-1)/2的情况。

断言3若图G是关于度偏差指数的极小值图且k＜(n-1)/2,则极小值图G中不存在端点度大于3的内部路。

证明(断言3) 假设存在端点v1,v2的度大于3的内部路P。不妨设d(v1)＞3,由仙人掌图的定义可知去掉v1之后图G至少有3个分支G1,G2,G3。设v1,v2,va∈V(P),且满足v1～va。又因极小值图G中必存在1个二度顶点v3,不失一般性地设v3∈V(G3)。设G＇由图G去掉边v1va和增加边v3va所得,即G＇=G-v1va+v3va,如图7 所示。显然图G＇中dG＇(v3)＞2,即减少1个二度顶点,由引理1得s(G)-s(G＇)=2(2k-2)/n＞0。故与假设矛盾。由此可得极小值图G中内部路的端点度等于3。

当k＜(n-1)/2时,由上知极小值图G的度序列只能是(2,…,2,3,…,3,4,…,4),此时度为2,3,4的顶点个数不知,下面我们继续寻找极小值图G对应的度为2,3,4的顶点个数。

断言4若图G是关于度偏差指数的极小值图且圈的个数k＜(n-1)/2,则极小值图G中不存在围长大于3的圈与其它圈共点。

证明(断言4) 假设图G中存在一个围长大于3的圈C1与另一个圈C2共点。设v1是其共享顶点,v1,v2,v3∈V(C1) 且v1～v2,v1～v3。设图G＇由图G去掉边v1v3和增加边v2v3，即G＇=G-v1v3+v2v3,如图8所示。

下面分d(v2)＞2和d(v2)=2 2种情况考虑。当d(v2)＞2时,则图G中n1,n2无变化且有dG＇(v2)＞3,但由断言3可知极小值图G中不存在端点度大于3的内部路,故与假设矛盾;当d(v2)=2时,显然图G＇中dG＇(v2)＞2,即减少1个二度顶点,由引理1得s(G)-s(G＇)=2(2k-2)/n＞0。故与假设矛盾。由此可得极小值图中围长大于3的圈必与内部路相连或若2个圈共点,则圈必是三角形。

断言5若图G是关于度偏差指数的极小值图且n/3＜k＜(n-1)/2,则极小值图G中不存在长度大于1的内部路和围长大于3的圈。

证明(断言5) 假设存在长度大于1的内部路和围长大于3的圈。因为图G中可能存在围长大于3的圈,由断言3和断言4可知引理3中的v2满足d(v2)=2,则可通过缩圈把图G中所有的围长大于3的圈变成三角形且不改变s(G)的值,此时图G中只存在长度大于1的内部路。设一条长大于1的内部路为P,则肯定存在2个共点的三角形和内部路P在一条链L上。(1)若P与2个共点的三角形相邻,设v2是其共享顶点,v1,v2∈V(P)且v1～v3,v2～v3,v2～v4,设图L＇由图L去掉边v3v4和增加边v3v1,即L＇=L-v3v4+v3v1如图9所示。显然L＇中dL＇(v1)＞ 2,即减少 1 个二度顶点,由引理1得s(G)-s(G＇)=2(2k-2)/n＞0,故与假设矛盾。(2)若P与2个共点的三角形不相邻,则在链L上找到离P最近的2个共点的三角形,设v1,v2∈V(P)且v2是离2个共点的三角形最近的P的1个端点和v1～v2,va,vb,vc是离v2最近的2个共点的三角形上的3个点。去掉边vavb、vavc,把va往P处滑动再添加边v1va、v2va,然后再把va所经过的所有三角形往右边滑动一格,此时得到L＇,如图10所示。显然L＇中dL＇(v1)＞2,即减少1个二度顶点,由引理1得s(G)-s(G＇)=2(2k-2)/n＞ 0。故与假设矛盾。所以通过图9、10的变换可以把图G中所有长度大于1的内部路变成全部长度为1的内部路,使得s(G)的值变小,此时可得到极小值图G的度序列是(2,…,2,3,…,3,4,…,4),其中n2=k+2,n3=2(n-2k-1),n4=3k-n。

断言6若图G是关于度偏差指数的极小值图且,则极小值图G中不存在2个共点的三角形。

证明(断言6) 假设存在2个共点的三角形。因为图G中圈比较少,则可通过断言5中的图9、10的变换把所有的共点的三角形拆分掉。故与假设矛盾。此时图G再无四度顶点,则可得到极小值图G的度序列是(2,…,2,3,…,3),其中n2=n-2k+2,n3=2k-2。