图的哈密尔顿性的Aα-谱条件
何 焕,叶淼林
(安庆师范大学 数理学院,安徽 安庆 246133)
本文考虑的所有图都是简单无向图。设G=(V,E)为n阶图,其顶点集V=V(G)={v1,v2,v3,…,vn},边集E=E(G)={e1,e2,e3,…,em}。图G的邻接矩阵记为A(G),图G的度对角矩阵记为D(G)。图G的顶点v的度是指G中与v关联的边数目,用dG(v)表示,记δ为G的顶点的最小度。记Kn、K1,n-1、Km,n-m分别是n阶完全图、星图、完全二部图。文献[1]最先给出了Aα-谱的概念,对于任意的实数α∈[ 0,1 ],称Aα(G)=αD(G)+( 1-α)A(G)为图G的Aα-矩阵。设Aα(G)的n个特征值从大到小排列为λ1(Aα(G))≥λ2(Aα(G))≥λ3(Aα(G))≥…≥λn(Aα(G)),最大特征值λ1(Aα(G))称为G的Aα-谱半径,记为λ(Aα(G))。设G1=(V1,E1)与G2=(V2,E2)是两个顶点不交的图,它们的并图为G1⋃G2=(V1⋃V2,E1⋃E2),又记为G1+G2;
它们的联图记为G1∨G2,即在G1+G2中添加由G1中每个顶点到G2中每个顶点的边所构成的图。一条包含图G中所有顶点的路称为哈密尔顿路,如果图G中任意两个顶点都被一条哈密尔顿路相连,则称G是哈密尔顿-连通的。一个包含图G中所有顶点的圈被称为哈密尔顿圈。如果图G包含一个哈密尔顿圈,则称G是哈密尔顿图。如果图G含有哈密尔顿路,则称G是可迹图。文中没有提到的概念和术语可参考文献[2]。
图的哈密尔顿问题是一个经典且困难的问题,近几年来关于这类问题的研究较多。Fiedler等根据图的邻接矩阵或其补图的谱半径给出了图含有哈密尔顿路或哈密尔顿圈的充分条件[3]。周波利用图的补图的无符号拉普拉斯矩阵的谱半径,给出了图包含哈密尔顿路和哈密尔顿圈的一些条件[4]。Butler等建立了一个图是哈密尔顿的充分条件,即拉普拉斯矩阵的非平凡特征值充分接近于图的平均度[5]。余桂东等根据图的邻接矩阵或无符号拉普拉斯矩阵或其补图的谱半径,给出了图是哈密尔顿-连通的一些谱充分条件,同时利用无符号拉普拉斯谱半径,给出了图含有哈密尔顿路或哈密尔顿圈的条件[6]。受文献[6]启发,本文给出了具有最小度数条件的连通图是哈密尔顿-连通的、哈密尔顿的和可迹的谱充分条件。
下面介绍需要用到的相关概念和引理。
给定一个含n个顶点的图G,如果对应于Aα-特征向量X={X1,X2,X3,…,Xn}T的特征值是λ,则根据Aα-特征值的定义,当且仅当X≠0,且对于每个u,v,显然矩阵的特征等式为
受无符号拉普拉斯谱半径与哈密尔顿性的启发,本文想要寻找Aα-谱半径与哈密尔顿-连通性之间的关系,又因为利用图的边数去刻画谱充分条件比较简单,所以借助上面的引理条件得到了下面的结论。
假设G不是哈密尔顿-连通的,则由引理2可得G∈NP1。
如果G=K4∨4K1,则设X={X1,X2,X3,…,X8}T是Aα(G)的特征值λ(Aα(G))所对应的特征向量。由图G的Aα-特征等式(1)可知,所有度为7的顶点在X中对应的值相同,记为X1;
所有度为4的顶点在X中对应的值相同,记为X2。仍由图G的Aα-特征等式(1),令λ=λ(Aα(G)),有
将式(2)转化成矩阵等式(B-λI)X′=0,这里X′=(X1,X2)T,
如果G=K4∨(K1,4+K1),则设X={X1,X2,X3,…,X10}T是Aα(G)的特征值λ(Aα(G))所对应的特征向量。由图G的Aα-特征等式(1)可知,所有度为9的顶点在X中对应的值相同,记为X1;
所有度为8的顶点在X中对应的值相同,记为X2;
所有度为5的顶点在X中对应的值相同,记为X3;
所有度为4的顶点在X中对应的值相同,记为X4。仍由图G的Aα-特征等式(1),λ=λ(Aα(G)),有
将式(3)转化成矩阵等式(B-λI)X′=0,这里X′=(X1,X2,X3,X4)T,
如果G=K3∨(K1,3+K1),则设X=(X1,X2,X3,…,X8)T是Aα(G)的特征值λ(Aα(G))所对应的特征向量。由图G的Aα-特征等式(1)可知,所有度为7的顶点在X中对应的值相同,记为X1;
所有度为6的顶点在X中对应的值相同,记为X2;
所有度为4的顶点在X中对应的值相同,记为X3;
所有度为3的顶点在X中对应的值相同,记为X4。仍由图G的Aα-特征等式(1),令λ=λ(Aα(G)),有
目前,利用邻接谱半径、无符号拉普拉斯谱半径、拉普拉斯谱半径去刻画图的哈密尔顿-连通性、哈密尔顿性和可迹性是十分常见的,比如文献[6]就是利用无符号拉普拉斯谱半径去刻画图的哈密尔顿性。但是,利用Aα-谱半径去刻画图的哈密尔顿-连通性、哈密尔顿性和可迹性的文献较少。本文借助文献[6]的思想,通过刻画Aα-谱半径,给出了具有最小度数条件的连通图是哈密尔顿-连通的、哈密尔顿的和可迹的谱充分条件。今后,希望可以找到一种较为合适的方法来利用Aα-谱半径去判断图的这些性质,从而优化本文中的一些结论。
猜你喜欢拉普拉斯充分条件等式集合、充分条件与必要条件、量词新世纪智能(数学备考)(2021年9期)2021-11-24组成等式数学小灵通(1-2年级)(2020年9期)2020-10-27有限μM,D-正交指数函数系的一个充分条件数学年刊A辑(中文版)(2019年4期)2019-12-16一个连等式与两个不等式链新高考·高一数学(2018年5期)2018-11-22浅谈充分条件与必要条件新课程·中旬(2016年11期)2017-02-10基于超拉普拉斯分布的磁化率重建算法现代计算机(2016年11期)2016-02-28一个等式的应用考试周刊(2015年105期)2015-09-10位移性在拉普拉斯变换中的应用中央民族大学学报(自然科学版)(2014年2期)2014-06-09p-超可解群的若干充分条件郑州大学学报(理学版)(2014年4期)2014-03-01具有吸收项和局部源的一维p-拉普拉斯方程解的熄灭郑州大学学报(理学版)(2014年3期)2014-03-01栏目最新:
- 2024年度在理论学习中心组关于群众路线...2024-01-16
- 在退役军人事务工作领导小组会议上讲话...2024-01-15
- 中秋国庆队伍教育管理工作动员部署会议...2024-01-15
- 2024年度区委书记在文旅农康融合发展大...2024-01-14
- 医院纪检监察干部队伍教育整顿个人党性...2024-01-14
- 教师演讲稿:牢记育人使命,涵养高尚师德...2024-01-13
- 2024年组织部长在市委理论学习中心组专...2024-01-13
- 2024年区人民法院案件质量评查办法(2篇...2024-01-13
- 2024年区长在指导某街道干部作风建设动...2024-01-11
- 在公司成立周年大会上讲话(3篇)(完整...2024-01-10
相关文章: