可迹图的一些新充分条件.pdf

2024年3 月Mar.,2024DOI:10.15960/ki.issn.1007-6093.2024.01.011刘珍珍1王礼想1李青2摘要 设图 G 是一个简单连通图,e(G)、(G)和 q(G)分别为图 G 的边数、谱半径和无符号拉普拉斯谱半径。如果一个图含有一条包含所有顶点的路，则这条路为哈密尔顿路，称这个图为可迹图。本文主要研究利用 e(G)、(G)和q(G)分别给出图G 是可迹图的一些新充分条件，所得结果推广了已有的结论。关键词图，可迹图，边数，谱半径，无符号拉普拉斯谱半径中图分类号0 157.52010数学分类号0 5C50,05C38,15A18Some new sufficient condition on traceable graphs*YU Guidongl,2,tLI Qing?Abstract Let G be a simple connected graph,e(G),(G)and q(G)be the edgenumber,the spectral radius and the signless Laplacian spectral radius of the graph G,respectively.If a graph has a path which contains all vertices of the graph,the path iscalled a Hamilton path,the graph is called traceable graph.In this paper,we presentsome new suficient conditions for the graph to be traceable graph in terms of e(G),(G)and q(G),respectively.The results generalize the existing conclusions.Keywords graphs,traceable graph,edge number,spectral radius,signless Laplacianspectral radiusChinese Library Classification O157.52010 Mathematics Subject Classification 05C50,05C38,15A18本文讨论的图都是简单无向连通图，令G是具有顶点集V=V(G)=u1,U2，U n 和边集 E=E(G)=e1,e2,em)的连通图,其中 IV(G)=n,|E(G)|=m(或 e(G)。若uiEV(G)，令d;=d(ui）表示顶点;的度，并设（di,d2,dn）是图G的度序列，其中did2d n。为了方便起见，我们用（,1 1,km，n m）来表示图G的度序列，其中是图G中度为k的顶点的个数。用(G)（或)表示G的最小度，即=d1。用Ks,t表示一个完全二部图，它的两个分部分别有s,t个顶点。简单图G和H的并是点集为 V(G)UV(H),边集为 E(G)UE(H)的图,记作 GUH,如果 G 和 H 不交,收稿日期：2 0 2 0-11-2 0*基金项目：国家自然科学基金（No.11671164)，安徽省自然科学基金（No.1808085MA04)，安徽省高校自然科学基金（Nos.KJ2020A0894，K J2 0 2 1A 0 6 50)，安徽高校研究生科学研项目（No.YJS20210515)，合肥幼儿师范高等专科学校科研创新团队（No.KCTD202001)1安庆师范大学数理学院，安徽安庆2 46 13 3；School of Mathematics and Physics，A n q i n g No r ma lUniversity,Anqing 246133,Anhui,China2.合肥幼儿师范高等专科学校公共教学部，安徽合肥2 3 0 0 13;DepartmentofPublic Teanching，H e f e iPreschool Education College,Hefei 230013,Anhui,China+通信作者E-mail:这筹学学报（中英文)Operations Research Transactions可迹图的一些新充分条件余桂东1,2,tLIU Zhenzhen1第2 8 卷第1期Vol.28No.1WANG Lixiangl132我们把它们的并称作不交并，通常记作G+H，k 个图的不交并用kG表示。GH 中，通过加上使 G中每一个点和 H 的每一个点相连的边，这样得到的图称作G和 H的联,用GVH表示。令A(G)表示图G的邻接矩阵，这里 A(G)是一个n 阶矩阵（ai),如果顶点u;和uj相邻，那么 ai=1,否则ai=0。显然 A(G)是一个非负的（0,1)实对称矩阵。因此，它所有的特征值都是实数。我们称A(G)的最大特征值为图G的谱半径，用(G)来表示。设 D(G)=diag(d(u1),d(u2),d(un)是图 G 的度对角矩阵。定义图 G 的无符号拉普拉斯矩阵 Q(G)=D(G)+A(G)。Q(G)的最大特征值q(G)被称为图的无符号拉普拉斯谱半径。包含图的每一个顶点的路称作哈密顿路，包含哈密顿路的图称为可迹图。近年来，利用谱图理论研究图的哈密顿问题得到了广泛的关注。对于图的哈密顿性和可迹性，已得出了一些好的充分条件。2 0 10 年，Fiedler和Nikiforov1首先给出可迹图与哈密尔顿图的谱半径条件。接着周波 2 从补图的无符号拉普拉斯的谱半径出发，研究了图的哈密顿性和可迹性的充分条件。陆玫等 3 研究了二部图是哈密顿图的谱充分条件。余桂东和范益政 4 给出了图是哈密顿连通图的一些谱条件。刘瑞芳等在文献 5中进一步研究了图或二部图是哈密顿图或可迹图的谱充分条件。周倩楠等 6 研究了一个图是哈密顿连通图或从任意一点出发都是可迹图的谱半径条件和无符号拉普拉斯谱半径条件。贾会才等 7 研究了补图的邻接谱半径条件和距离无符号拉普拉斯半径条件，拓展和改善了文献 6 中的相关结果。特别是，宁博等在文献 8 中研究了可迹图的边充分条件和谱充分条件。受此启发，本文继续研究可迹图的充分条件，其结论优化了前期的结论。余桂东，刘珍珍，王礼想，李青28卷1准备工作我们先把文中需要用到的一些图画出，如下图所示：CG3XG1oG11G4G6G12G13G14G15G16G17G18G19G20G21G22G23G24G31125G32G26G33G27G34G28G35G29K.1G36G30G371期NP=K2 V(3K1+K3),Kg V(4K1+K2),Ki V(2K1+2Ki V Kn-5),G18,G37,K2 V K2,6,Ki V(Kn-3+2Ki),K2 V G13,K3 V(Ki+Ki,5),K4 V6K1,2KiV(K2+3K1),K1 VG3,Ki VG2,K2 V5K1,K1 V(K+Ki V(K2+2K1),K2 V(3Ki+K2),Ki V(K2 V4Ki+K1),K2 V(2Ki+K1,3),Ki VG19,Ki VG22,G23,G26,K2 V(K1,4+K1),Ki V K2,5,K3 V5K1,G6,K1 V(2K1+K1,2),Ki V(2K2+K1),Gs,K1 V(K1,3+K1),K2,4,Ki V(K2+K1,2),K2 V4Ki)。NP2=K1 V(Kn-3+2K1),K4 V6K1,K2 V(3Ki+K2),K2 V(K1,4+K1),K1 VK2,5,K3 V5K1,Ki(K1,3+K1),K2,4,K2 V4Ki)。NP3=Ki V(Kn-3+2Ki),Ki V(K1,3+Ki),K2,4,K2 V 4K1,K2 V(3K1+K2),G6,Ki V(2K2+Ki),Ki V(2Ki+Ki,2),Ki V(K2+Ki,2),G37)。NP4=Ki V(Kn-3+2Ki),Ki V4K1,Ki V(2K1+2Ki V Ki),K4 V6K1,K2 V5K1,K2 V(3Ki+K2),K2 V(K1,4 VKi),K3 V5Ki,Ki V(2Ki+Ki,2),Ki V(Ki1,3+Ki),Ki V(K2+Ki,2),K2 V4Ki)。引理1 9】设 G 是一个度序列为(di,d2,dn）的图，其中 diddn且n4。如果不存在整数 ，使得dk-1且dn-k+1n-1,则图是可迹图。若存在一个简单图的度序列为（d,d2,dn)，则称序列（di,d,dn）是可图的。引理2 10)设G是一个连通图,其顶点数为n,边数为m,则(G)V2m-n+1,其等式成立当且仅当G=Kn或 G=K1,n-1。引理3 4)设 G是一个简单图,其顶点数为n，边数为m，则q(G)+n-2,如果G是连通图，那么等式成立当且仅当G=Kn或G=K1,n-1；否则等式成立当且仅当G=Kn-1+U。2主要结论定理1 设G 是一个连通图,其顶点数为n(n4),边数为m,如果m（)+1,则G是可迹图,除非GE NPi。证明假设不是可迹图，则由引理1知，存在一个整数4时，该图是可迹的，n=4时，该图是不连通的,矛盾。当可图序列为(12,(n-4)2,(n-3)n-5,(n-1)时，即G=KiV(2K1+2KiVKn-5)。易知该图是不可迹的。当可图序列为(12,（n4)，（n-3)n-4,（n 2)）时，即图为两个度为1的点与2 K1VKn-4中一个度为n4的点相邻，记为G18，易知该图是不可迹的；或G=G36，易知n5时，该图是可迹的，n=5时，该图是不可迹的，记为G37。情形3.1.2:2 m=(n-2)(n=3)+4。此时可图序列为(12,(n-3)n-3,(n-1)，即G=KiV(2Ki+Kn-3)。易知该图是不可迹的。情形3.2:2 n-3k=5=0,由k，则n13,则n=10,k=5或n=7,=3,分以下两种情况讨论：情形3.2.1:n=10,k=5。此时ds4,ds4，此时58 2 m60。分成下面两种情况讨论(具体见表1):度和序号5812603(i）当2 m=58时，有可图序列：（4,8 2,9 2)或（3 1,45,8 1,9 3)。当可图序列为（46,8 2,9 2）时，若两个度为8 的点不相邻时，即G=K2VK2,6；若两个度为8 的点相邻时,即G=K2VG13余桂东，刘珍珍，王礼想，李青(k-2)(2n-3k-5)-2 0,表1情形3.2.1的度序列和相对应的图度序列(46,82,92)(31,45,81,93)(46,94)28卷图不可迹图K2VK2,6,K2VG13K2VK2,6,K2 VG13K3 V(Ki+K1,5)K3 V(Ki+K1,5)K4V6KiK4V6Ki1期当可图序列为(3 1,45,8 1,9 3)，即G=K3V(K1+K1,5)。(i)当2 m=60时，有可图序列：（46,9 4)，即G=K4V6K1。情形3.2.2:n=7,k=3.此时ds2,ds3，且2 2 2 m24，分成下面两种情况讨论(具体见表2):度和序号2212345(11,22,32,51,61)246(i)当2 m=22时，有可图序列：(2 3,3 2,52)或（2 3,3 2,41,6 1）或(2 4,3 1,51,6 1或（2 5,6 2)或(11,2 2,3 2,51,6 1)。当可图序列为(2,3 2,52)时。若两个度为5的点不相邻时，即G=2K1V(K2+3K1);若两个度为5的点相邻但两个度为3 的点不相邻，即G=G或G=G11；若两个度为5的点相邻且两个度为3 的点也相邻，即G=G12。当可图序列为(2 3,3 2,41,6 1)时。若两个度为3 的点不相邻时，即G=K1VG3;若两个度为3 的点不相邻但三个度为2 的点互不相邻时，即G=K1VG1;若两个度为3 的点不相邻且三个度为2 的点有相邻时,即G=KiV(K2+Ki(K1+K2)。当可图序列为(2 4,3 1,51,6 )时，即G=KiVG2。当可图序列为(2 5,6 2)时,即G=K2V5K1。当可图序列为(11,2 2,3 2,51,6 )时，即G=Ki(K1+Ki(K2+2K1)。(i)当2 m=24时，有可图序列：（2 3,3 2,6 2)，即G=K2V(3K1+K2)。情形 4:(k-2)(2n-3k-5)0,则有 k3,2n-3k-50,又由k-2g-，即m-2g-a+1.则由定理1可知G是可迹图，除非GeNP。下面验证NPi中的图是否满足定理条件。给定一个n 阶图 G,对于向量 X R,如果存在一个从 V(G)到 X中的值的一一映射,使得对于任意的uE V(G),有(u)=au,则称 X 定义在 G 上,如果 X 是 A(G)可迹图的一些新充分条件表4情形4.2 的度序列和相对应的图度序列(25,4)(24,32)(12,2,42)(12,22,31,51)(11,24,5)(1,23,31,4)(11,23,41,5)(24,42)(24,31,5)(24,52)137图不可迹图G4可迹G5,G16,G17可迹GG6Ki V(2Ki+K1,2)Ki V(2Ki+K1,2)Ki V(2K2+K1)Ki V(2K2+K1)Gs,Gg,G10,G15G8Ki V(Ki+Ki,3)Ki V(K1,3+K1)K2,4,G14K2,4Ki V(K2+K1,2)Ki V(K2+Ki,2)K2V4K1K2V4K1口(2)138的特征值对应的一个特征向量,X中的元素u与图 G中的点u对应。我们有这里 Nc(u)定义为在G中的邻集。等式(3)被称为图G的特征方程。若 G=Ki(Kn-3+2Ki),其中 n5。设 X=(i,a2,an)T 为(G)对应的一个单位特征向量。于是有由式(3）知，所有度为1的点都有相同的分量，记为X1；所有度为n一3 的点都有相同的分量c，记为X2；度为n一1的点的分量，记为X3。则由特征方程(3)，我们有因而，(G)为下面方程最大的根：f()=3(4n)a(1n)+2 n 8。且f(a)=3a+2(4-n)+1-n。得到两个根1和a2,使得f(a1)=f(z2)=0,n-4-Vn2-5n+31.=3因此,当n-6时,f()0;故f()是单调递增的,而当n5时,f(Vn-6n+7)Vn-6n+7。同理，借助于WolframAlpha(http:/ V(3K1+K3)K3 V(4Ki+K2)K2VK2,6K2VG13K3 V(K1+K1,5)K4V6K12K1V(K2+3K1)KiVG3Ki VG2K2V5K1Ki V(Ki+Ki V(K2+2Ki)K2 V(3K1+K2)KiV(K2V4K1+K1)K2 V(2K1+K1,3)KiVG19根据表5和证明过程，可知在 NPi中除了G NP外，其余的图都满足(G)Vn2-6n+7。口余桂东，刘珍珍，王礼想，李青uCu=auuENG(u)(G)=XTA(G)X。(G)X1=X3;(G)X2=(n-4)X2+X3;(G)X3=2Xi+(n-3)X2。C2=3表5NPi中其他图的谱半径M(G)Vn2-6n+74.605 64.79585.50905.83106.325 96.85566.36396.85566.45336.855 66.62356.85563.41423.74173.52013.74173.446 43.74173.701 63.74173.700 93.741 73.90953.741 74.65275.38524.57965.385 24.56405.385 228卷(3)n-4+Vn-5n+3(n3,则 G 是可迹图,除非 G E Ki V(Kn-3+2K1),K1V(K1,3+K1),K2 V4K1)。注：定理4是目前研究可迹图谱条件的最新结论。易知，除了特殊的几个图外，定理3优化了定理4。受此启发，下面我们进一步研究可迹图的无符号拉普拉斯的谱充分条件。定理 设 是一个连通图,其顶点数为 n(n4),如果q(G)+2n-6,则 G是可迹图,除非GENP4。证明由定理条件与引理3 知，2元1+2 m 6(G)显然,当 G=Kn 时,q(G)=2n-1+2n-6;当 G=K1,n-1时,q(G)=n 高+2 m-6.因此,)式中等式不能同时成立,则有m-2g-2,即m-2g-+1则由定理1可知G是可迹图，除非GENPi。下面验证NPI中的图是否满足定理条件。如果X是Q(G)的特征值对应的一个特征向量，X中的元素 u与图G中的点u对应。我们有(5)uENc(u)等式（5）被称为图G的无符号拉普拉斯特征方程。若G=Ki(2Ki+Kn-3),其中 n4。设X=(a1,2,an)T为q(G)的一个单位向量。于是,有由（5）式知，所有度为1的点都有相同的分量，记为Xi；所有度为n3 的点都有相同的分量c，记为X2;度为n1的点的分量，记为X3。由特征方程(5)式，我们有(g(G)-1X1=X3;q(G)-(n-3)X2=(n-4)X2+X3;(q(G)-(n-1)X3=2Xi+(n-3)X2。因而,q(G)即为下面方程最大的根：g(）=3+(7-3 n)+(2n-7n)-2n+14n-24,且g(c)=3+(14-6n)+2n-7n,得到两个根1和2，使得g(1)=g(2)=0,3n-7-V3n-21n+49a1=3可迹图的一些新充分条件2m+n-2。n-12q-dc(u)u=q(G)=XTQ(G)X。2=139(4)23n-7+V3n2-21n+493O因此,当2时,g(c)0,故g(a)是单调递增的。而当n4时,g(+2n-6)+2n-6。同理，借助于WolframAlpha(http:/ G=KiV4K1或G=KiV(2K1+2KiVK1);当n7时,q(Kiv(2K1+2KiVKn-5)音+2 m-6,矛盾。q(G1s)吾+2 m-6,矛盾。通过同样的方法，我们可以得到NPi中其他图的无符号拉普拉斯谱半径谱半径，如下表6 所示。140GK2 V(3K1+K3)K3 V(4K1+K2)K2V K2,6K2VG13K3 V(Ki+K1,5)K4V6K12K1V(K2+3K1)KiVG3KiVG2K2V5K1Ki V(Ki+Ki V(K2+2Ki)K2 V(3K1+K2)K1 V(K2V4K1+K1)K2 V(2K1+K1,3)K1 VG19根据上表和证明过程，可知在 NPI中除了GE NP4外，其余的图都满足 q(G)1+2n-6。2余桂东，刘珍珍，王礼想，李青表6 NPi中其他图的无符号拉普拉斯谱半径q(G)2n-1+2n-6G10.172310.285712.150512.250013.640 214.222213.732.414.222214.000014.222214.324614.22207.328 08.33337.91428.33337.86138.33338.5311.8.33334.59918.33338.73558.333310.118210.285 710.172310.285 710.026710.285728卷q(G)n1+2n-6KiVG229.6901G239.4106G269.067 1K2 V(K1,4+K1)10.492 1KiV K2,510.000 0K3V5K110.8990G66.1563Ki V(2K1+K1,2)6.4940Ki V(2K2+K1)6.3723G85.514 1Ki v(K1,3+K1)7.1172K2,46.0000Ki V(K2+K1,2)6.626 2K2V4K17.4641G374.170110.285710.285710.285710.285 710.285 710.285 76.40006.40006.40006.40006.400 06.40006.400 06.40004.5000口参考文献1 Fiedler M,Nikiforov V.Spectral radius and Hamiltonicity of graphs J.Linear Algebra andIts Applications,2010,432:2170-2173.2 Zhou B.Signless Laplacian spectral radius and Hamiltonicity J.Linear Algebra and Its Ap-plications,2010,432(2/3):566-570.3 Lu M,Liu H Q,Tian F.Spectral radius and Hamiltonian graphs J.Linear Algebra and ItsApplications,2012,437(7):1670-1674.4 Yu G D,Fan Y Z.Spectral conditions for a graph to be Hamilton-connected J.AppliedMechanics&Materials,2013,336-338:2329-2334.5 Liu R F,Shiu W C,Xue J.Sufficient spectral conditions on HamiltonianJ.Linear Algebraand Its Applications,2015,467:254-266.6 Zhou Q N,Wang L G.Some suficient spectral conditions on Hamilton-connected and traceablegraphs J.Linear and Multilinear Algebra,2017,65:224-234.7贾会才，薛杰。哈密顿连通图和可迹图的新充分谱条件。数学的实践与认识，2 0 17,47(11)：2 7 2-276.8 Ning B,Ge J.Spectral radius and Hamiltonian properties of graphs J.Linear and MultilinearAlgebra,2015,63(8):1520-1530.9 Bondy J A,Murty U S R.Graph Theory M.New York:Springer,2008.10 Yuan H.A bound on the spectral radius of graphs J.Linear Algebra and Its Applications,1988,108:135-139.