关于图的augmented Zagreb指数和色数

杜建伟,孙晓玲

(中北大学 理学院,山西 太原 030051)

0 引言

拓扑指数是从化合物的结构图衍生出来的不变量,它可以定量描述分子的结构,也可以分析相关分子的结构与性能或活性之间的关系,在理论化学、组合化学和应用化学的研究中都有着广泛的应用[1]。2010年,Furtula等[2]在研究辛烷和庚烷的生成热时首次提出了图G的augmented Zagreb指数(简称为AZI)的定义:

其中d(u)表示图G中顶点u的度。

本文所考虑的图G=(V(G),E(G))均为简单连通图,其中V(G)是G的顶点集,E(G)是G的边集。NG(u)(简写为N(u))表示G中顶点u的所有邻点构成的集合,dG(u)=|NG(u)|(简写为d(u))表示G中顶点u的度。用k种颜色对图G的顶点进行着色,且没有相邻的顶点着相同的颜色,则称为G的一个k-顶点着色。k-顶点着色简称为k-着色。使图G为k-着色的k的最小值称为G的色数,记作χ(G),简记为χ。Kn表示n个顶点的完全图。

设G和H是点和边不相交的图。V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪ {uv|u∈V(G),v∈V(H)},则称G∨H为G和H的联图。

Gn,l表示满足|ni-nj|≤1的具有n个顶点的完全l-部图,其中ni(i=1,2,…,l)是Gn,l第i部集的顶点数。

文中未加说明的术语或记号可参看文献[3]。

近年来,augmented Zagreb指数引起了许多数学家、化学家的关注, 并发表了大量理论与应用方面的文章。Furtula等[2]得到了化学树的augmented Zagreb指数的上界和下界,并且确定了树的augmented Zagreb指数的极小值。Huang等[4]给出了各类连通图augmented Zagreb指数的一些上下界,并刻画了相应的极图。Wang等[5]通过使用不同图形参数得到了连通图的augmented Zagreb指数的界及相应极图。Du等[6]得到了渺位六角系统augmented Zagreb指数的上下界及相应的极图,并确定了具有固定悬挂点数目的化学树的augmented Zagreb指数的最大值。Zhan等[7]给出了单圈图的极小和第二小augmented Zagreb指数,并且确定了双圈图的augmented Zagreb指数的极小值。更多有关augmented Zagreb指数的文章请见文献[8-16]。本文研究了χ≥2的n阶连通图G的augmented Zagreb指数,当n被χ整除时,得到了G的augmented Zagreb指数的一个上界,并刻画了极图。

1 主要结果

引理1[4]设G是阶为n≥3的连通图,且G≠Kn，则

AZI(G)

其中e∉E(G)。

定理1 设G是χ=2的n阶连通图，则

(i)当n为奇数时,

等号成立当且仅当G≅Gn,2;

(ii)当n为偶数时,

等号成立当且仅当G≅Gn,2。

AZI(G″)-AZI(G′)=(n1+1)(n2-1)

因此,AZI(G″)>AZI(G′),矛盾。故G′≅Gn,2.

证毕。

定理2 设G是χ≥3的n阶连通图,其中n可以被χ整除,则

AZI(G)≤AZI(Gn,χ),

等号成立当且仅当G≅Gn,χ。

证明考虑G的一种χ-着色。用ni表示第i种颜色集合中元素的数目,即ni为着第i种颜色的顶点数,i=1,2,…,χ。

由引理1可知G增加一条边会严格增加AZI(G),故

(1)

AZI(G)≤|〈a,b〉|≤‖a‖‖b‖,

(2)

其中‖a‖表示向量a的模。

(2)中|〈a,b〉|=‖a‖‖b‖成立当且仅当向量a和b线性相关,即a=λb成立,其中λ≠0。因此|〈a,b〉|=‖a‖‖b‖成立当且仅当对每一对i,j(1≤i

nj(n-nk)3(2n-ni-nk-2)3=

nk(n-nj)3(2n-ni-nj-2)3。

(3)

如果nj>nk,那么

(n-nk)3>(n-nj)3,

(2n-ni-nk-2)3>(2n-ni-nj-2)3,

于是

nj(n-nk)3(2n-ni-nk-2)3>

nk(n-nj)3(2n-ni-nj-2)3,

这与(3)矛盾。如果nj

nj(n-nk)3(2n-ni-nk-2)3<

nk(n-nj)3(2n-ni-nj-2)3,

推论1 设G是χ≥2的n阶连通图,其中n可以被χ整除，则

等号成立当且仅当G≅Gn,χ。

证明当χ=2时,由定理1中(ii)的结果,可知推论成立。

由(2),有