EDS指数与平衡二部图的哈密尔顿性

李 青,刘 莉,袁 慧

(1.合肥幼儿师范高等专科学校公共教学部,安徽 合肥 230013;2.安庆师范大学数理学院,安徽 安庆 246133)

0 引言

图G的邻接矩阵A(G)的最大特征值μ(G)称为图G的谱半径;图G的无符号拉普拉斯矩阵Q(G)的最大特征值q(G)称为图G的无符号拉普拉斯谱半径.在一个二部图G=(X,Y;E)中,若|X|=|Y|,则称此二部图为平衡二部图.对于平衡二部图G=(X,Y;E),如果X中任一点与Y中任一点之间均能找到一条哈密尔顿路,那么该平衡二部图称为弱哈密尔顿-连通图.

图G的离心距离和[5-6](Eccentric Distance Sum,EDS)是化学图论中基于离心率的拓扑指数.在连通图G中,图G的离心距离和ξd(G)定义为

LU等[7]根据图G的离心距离和给出了一个图是k-哈密尔顿、k-边哈密尔顿或k-路覆盖的充分条件.受文献[7]的启发,本文利用平衡二部图的度序列与边条件,根据原图或其拟补图的离心距离和分别提出了一个平衡二部图是可迹的、哈密尔顿或弱哈密尔顿-连通的充分条件.

1 相关引理

证明 设NG(x1)∶={z1,z2,…,zs}表示点x1的邻点集,这里s=dG(x1).那么对于任意的zi∈NG(x1),dG(x1,zi)=1;对于任意的xi(2≤i≤n),dG(x1,xi)≥2;对于任意的yi∈YNG(x1),dG(x1,yi)≥3.于是有

D(x1)≥dG(x1)+2(n-1)+3(n-dG(x1))=5n-2-2dG(x1).

类似地,对于任意的i(2≤i≤n)和任意的j(1≤j≤n),都有

D(xi)≥dG(xi)+2(n-1)+3(n-dG(xi))=5n-2-2dG(xi),
D(yj)≥dG(yj)+2(n-1)+3(n-dG(yj))=5n-2-2dG(yj).

于是,

类似地,对于任意的i(2≤i≤n)和任意的j(1≤j≤n),都有

2 主要结果

当e(G)≤n(n-k-2)+(k+2)2时.由引理5可知,

于是,

e(G)≤n(n-k-1)+k(k+1)-(n-k-1)-k

产生矛盾.

e(G)≤n2-2(n-1)-1=(n-1)2,

当n≥9时,图G也满足e(G)>n2-3n+9.

那么图G是哈密尔顿的.

当e(G)≤n(n-k-1)+(k+1)2时,由引理5可知,

于是得到

e(G)≤(n-k)2+nk-(n-k)-k

产生矛盾.

结合n≥2k-1,有

于是得到

于是得到

3 结语

本文利用平衡二部图的度序列与边条件,根据原图或其拟补图的离心距离和分别提出了一个平衡二部图是可迹的、哈密尔顿或弱哈密尔顿-连通的充分条件.今后,如果遇到了类似问题便可运用相同方法研究图的其他性质,这为研究图的结构性质提供了一种行之有效的方法.