具有n-4个悬挂点的双圈补图的最小特征值的下界.pdf

?41?1?2024?1?Journal of Xinjiang University(Natural Science Edition in Chinese and English)Vol.41,No.1Jan.,2024具有n4个悬挂点的双圈补图的最小特征值的下界周恋恋，刘 康，孟吉翔(?830017)摘要：?,?,?.?,?,?n4?n?.关键词：?;?;?;?DOI?10.13568/ki.651094.651316.2023.02.02.0002中图分类号：O157.5文献标识码：A文章编号?2096-7675(2024)01-0020-07引文格式：?n4?J?(?)(?)?2024?41(1)?20-26+36?英文引文格式：ZHOU Lianlian?LIU Kang?MENG Jixiang?The lower bounds of the least eigenvalue of complementsof bicyclic graphs with n4 pendant verticesJ?Journal of Xinjiang University(Natural Science Edition in Chineseand English)?2024?41(1)?20-26+36?The Lower Bounds of the Least Eigenvalue of Complements ofBicyclic Graphs with n4 Pendant VerticesZHOU Lianlian,LIU Kang,MENG Jixiang(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China)Abstract：The least eigenvalue as a parameter to characterize the structural properties of a graph,has importantresearch value.Comparing with the spectral radius,the least eigenvalue of a graph is less studied.The graphsin this paper are simple,undirected and connected,and we characterize the lower bounds of the least adjacencyeigenvalue of graphs in the set of bicyclic graphs with n vertices and n4 pendant vertices by using relevantknowledge analysis and demonstration.Key words：complement graphs;bicyclic graphs;least eigenvalue;lower bounds0概 念?,?G=(V(G),E(G)?V(G)?E(G)?,?V(G)=v1,v2,vn,E(G)=e1,e2,en.?Gc=(V(Gc),E(Gc),?V(Gc)=V(G),E(Gc)=vivj|vi,vjV(G),vivj/E(G).?G?A(G)=(aij)nn,?vi,vj?,aij=1;?aij=0.?A(G)?,?1(G)2(G)n(G),?n(G)?(G),?G?.?A-?.?Bn,n4?n4?n?,?Bcn,n4?.?,?.Johnsonc?1?n?k?,Liu?2?k?n?,Ye?3?n?.?,Fan?4?;Jiang?5?收稿日期：2023-02-02基金项目：?XJEDU2021I001?作者简介：?1997?E-mail?zhou ?通讯作者：?1962?E-mail?1?n4?21?.?,?Bcn,n4?.?,?6-10.1预备知识?G?V(G)=v1,v2,vn,?X=(Xv1,Xv2,Xvn)T?Xvi=X(vi)(1in),?XTA(G)X=2XuvE(G)XuXv(1)?G?v?v?,?NG(v),?v?d(v)=|NG(v)|.?X 6=0?G?,?viV?Xvi=XvjNG(vi)Xvj(2)?.?X Rn?(G)XTA(G)X(3)?X?G?.?Gc?G?.?A(Gc)=J IA(G)(4)?J,I?n?1?.引理111?A?nn?,B?A?mm?,?1(A)2(A)n(A),1(B)2(B)n(B)?A?B?,?i=1,2,m,?nm+i(A)i(B)i(A).2Bcn,n4中最小邻接特征值的下界?H?C3?,?V(H)=v1,v2,v3,v4,?dH(v2)=dH(v4)=3.?p,q,r?s?,?H6(p,q,r,s)?H?v1,v2,v3,v4?p,q,r?s?,?p+q+r+s=n4.?p,q,r?s?0,?H?,?r=0?s=0,?H4(p,q,s)?H5(p,q,r).?p,q,r?s?0,?H?,?p=r=0,q=s=0?r=s=0,?H1(q,s),H2(p,r)?H3(p,q)(?1).图 1有 n4 个悬挂点的双圈图引理2?p,q,s?p+q+s=n4.?n 7,?H H1(q,s),H3(p,q)?(Hc)(Hc4(p,q,s),?p,q?s?.证明?X?Hc4(p,q,s)?,vji?vj(j=1,2,3,4)?.?,?vj?.?H4(p,q,s)?v1,v2,v4?2?.情形1 Xv1 Xv4 Xv2(Xv2 Xv4 Xv1,Xv1 Xv2 Xv4?Xv4 Xv2 Xv1?).?v4?(?,Xv4i0,?Xv4iXv1Xv4iXv4Xv4iXv2),?22?2024?v1?H3(s+p,q),?(1)?XTA(Hc3(s+p,q)XXTA(Hc4(p,q,s)X=2sXv4i(Xv4Xv1)0,?(Hc4(p,q,s)(Hc3(s+p,q).?v4?(?,Xv4i 0,?Xv4iXv1Xv4iXv4Xv4iXv2),?v2?H3(p,s+q),?(1)?XTA(Hc3(p,s+q)XXTA(Hc4(p,q,s)X=2sXv4i(Xv4Xv2)0,?(Hc4(p,q,s)(Hc3(p,s+q).情形2 Xv2 Xv1 Xv4(Xv4 Xv1 Xv2?).?v1?(?,Xv1i0,?Xv1iXv2Xv1iXv1Xv1iXv4),?v2?H1(p+q,s),?(1)?XTA(Hc1(p+q,s)XXTA(Hc4(p,q,s)X=2pXv1i(Xv1Xv2)0,?(Hc4(p,q,s)(Hc1(p+q,s).?v1?(?,Xv1i 0,?Xv1iXv2Xv1iXv1Xv1iXv4),?v4?H1(q,s+p).?(1)?XTA(Hc1(q,s+p)XXTA(Hc4(p,q,s)X=2pXv1i(Xv1Xv4)0,?(Hc4(p,q,s)(Hc1(q,s+p).引理3?p,q,r?p+q+r=n4.?n 7,?H H2(p,r),H3(p,q)?(Hc)(Hc5(p,q,r),?p,q?r?.?2?,?3?.引理4?p,q,r?s?p+q+r+s=n4.?n8,?H H4(p,q,s),H5(p,q,r)?(Hc)(Hc6(p,q,r,s),?p,q,r?s?.证明?X?Hc6(p,q,r,s)?.?vji?vj(j=1,2,3,4)?.?,?vj?.?Xv1Xv3,?H6(p,q,r,s)?v1,v2,v3,v4?2?.情形1 Xv2 Xv1 Xv3 Xv4(Xv1 Xv2 Xv3 Xv4,Xv1 Xv4 Xv3 Xv2,Xv2 Xv4 Xv1 Xv3,Xv4 Xv1 Xv3 Xv2?Xv4 Xv2 Xv1 Xv3?).?v3.?v3?(?,Xv3i 0,?Xv3iXv2 Xv3iXv3 Xv3iXv4),?v2?H4(p,r+q,s),?(1)?XTA(Hc4(p,r+q,s)XXTA(Hc6(p,q,r,s)X=2rXv3i(Xv3Xv2)0,?(Hc6(p,q,r,s)(Hc4(p,r+q,s).?v3?(?,Xv3i 0,?Xv3iXv1Xv3iXv3Xv3iXv4),?v4?H4(p,q,s+r),?(1)?XTA(Hc4(p,q,s+r)XXTA(Hc6(p,q,r,s)X=2rXv3i(Xv3Xv4)0;?(Hc6(p,q,r,s)(Hc4(p,q,s+r).情形2Xv1 Xv3 Xv2 Xv4(Xv1 Xv2 Xv4 Xv3,Xv1 Xv3 Xv2 Xv4,Xv1 Xv3 Xv4 Xv2,Xv1Xv4Xv2Xv3,Xv4Xv1Xv2Xv3?Xv2Xv1Xv4Xv3?).?,?v3?1?,?v2.?v2?(?,Xv2i0,?Xv2iXv1Xv2iXv2Xv2iXv4),?v1?H5(p+q,r,s),?(1)?XTA(Hc5(p+q,r,s)XXTA(Hc6(p,q,r,s)X=2qXv2i(Xv2Xv1)0,?1?n4?23?(Hc6(p,q,r,s)(Hc5(p+q,r,s).?v2?(?,Xv2i 0,?Xv2iXv1Xv2iXv2 s 1?,?(Hc1(q,s)(Hc1(q1,s+1).证明?X?Hc1(q,s)?.?K2,2Hc1(q,s)?(K2,2)=2,?1?(Hc1(q,s)2.?,v2?v4?q?s?,?X5?X6,?Xvi=Xi(i=1,2,3,4).?(2)?:X1=X3+qX5+sX6,X2=sX6,X3=X1+qX5+sX6,X4=qX5,X5=X1+X3+X4+(q1)X5+sX6,X6=X1+X2+X3+qX5+(s1)X6.?(EB)X=0,?X=X1X2X3X4X5X6,B=0010qs00000s1000qs0000q01011q1s1110qs1.?PHc1(q,s)=(x+1)n6f(x;q,s),?f(x;q,s)=det(EB),?f(x;q,s)=x6+(2qs)x5+(4q4s)x4+(24q4s+2qs)x3+(5qs1)x2+(q+s+2qs)xqs.?,?f(x;q,s)=0?.f(x;q1,s+1)f(x;q,s)=(qs1)(x+1)(x(2x+3)1).?qs10,?2,?f(x;q1,s+1)f(x;q,s)=(qs1)(x+1)(x(2x+3)1)0.?n?,PHc1(q1,s+1)PHc1(q,s)0,?(Hc1(q,s)(Hc1(q1,s+1).?5,?1?.推论1?q,s?q+s=n4.?n8,?(Hc1(q,s)(Hc1(n4)/2,(n4)/2),?H1(q,s)=H1(n4)/2,(n4)/2).引理6?n(n 10),?p,r?p+r=n4.?p r 0?,?(Hc2(p,r)(Hc2(p1,r+1).证明?X?Hc2(p,r)?.?r 0,?K2,3 Hc2(p,r)?(K2,3)=6,?1?(Hc2(p,r)6.?,v1?v3?p?r?,?X5?X6,?Xvi=Xi(i=1,2,3,4).?(2)?:X1=X3+rX6,X2=pX5+rX6,X3=X1+pX5,X4=pX5+rX6,X5=X2+X3+X4+(p1)X5+rX6,X6=X1+X2+X4+pX5+(r1)X6.?(EB)X=0,?24?2024?X=X1X2X3X4X5X6,B=00100r0000pr1000p00000pr0111p1r1101pr1.?PHc2(p,r)=(x+1)n6f(x;p,r),?f(x;p,r)=det(EB),?f(x;p,r)=x6+(2pr)x5+(4p4r)x4+(22p2r+2pr)x3+(1+3p+3r+3pr)x2+(2p+2r4pr)x.?,?f(x;p,r)=0?.f(x;p1,r+1)f(x;p,r)=(pr1)x(2x2+3x4).?pr10,?x6,?f(x;p1,r+1)f(x;p,r)=(pr1)x(2x2+3x4)0.?n?,PHc2(p1,r+1)PHc2(p,r)0,?(Hc2(p,r)(Hc2(p1,r+1).?r=0,?X1=X3,X2=pX5,X3=X1+pX5,X4=pX5,X5=X2+X3+X4+(p1)X5.?(EB)X=0,?p+r=n4,?X=X1X2X3X4X5,B=001000000p1000p0000p0111p1.?PHc2(n4,0)=(x+1)n5f(x;n4,0),?f1(x;n4,0)=det(xE B),?f1(x;n4,0)=x5+(n5)x4+(3n11)x3+(5n)x2+(82n)x,?f1(x;n4,0)=0?.?x=1/4413 2.350 78?,f1(2.350 78;n4,0)=70.820 39.258 5n.?n 8?,f1(2.350 78;n4,0)0,?,10?xn2?,y(n2)=2n2+(4n2+36n80)n2+13n260.?,?x 0,?g(x)f2(x;n5,1)0.?,(Hc2(n4,0)(Hc2(n5,1).?6,?2?.推论2?p,r?p+r=n4.?n10,?(Hc2(p,r)(Hc2(n4)/2,(n4)/2),?H2(p,r)=H2(n4)/2,(n4)/2).引理7?p,q?p+q=n4.?pq 0?,?:(i)?n13?,?(Hc3(p,q)(Hc3(n1)/2,(n7)/2),?p=(n1)/2,q=(n7)/2;(ii)?n18?,?(Hc3(p,q)(Hc3(n2)/2,(n6)/2),?p=(n2)/2,q=(n6)/2.证明?p+q=n4,?p,q?,?PHc3(p,q)=(x+1)n6f(x;p,q),?f(x;p,q)=det(EB).(i)?n?,PHc3(p+q+3)/2,(p+q3)/2)PHc3(p,q)=(x+1)n6(f(x;(p+q+3)/2,(p+q3)/2)f(x;p,q).f(Hc3(p+q+3)/2,(p+q 3)/2)(2.8)0,?(Hc3(p+q+3)/2,(p+q 3)/2)2.8.?x 2.8?,f(x;(p+q+3)/2,(p+q3)/2f(x;p,q)=1/4(pq3)(2(pq+1)x3+(5p5q+9)x2+(pq+1)xp+q3)0.?,1/4(pq3)0,?x2.8?,y(x)=2(pq+1)x3+(5p5q+9)x2+(pq+1)xp+q3 2.8,?y(2.8)=2.36+20.04(pq)0,?x2.8?,y(x)?,?y(2.8)=20.8568.504(pq)0.?y(x)0?pq=3,?PHc3(p+q+3)/2,(p+q3)/2)PHc3(p,q)0.(ii)?n?,PHc3(p+q+2)/2,(p+q2)/2)PHc3(p,q)=(x+1)n6(f(x;(p+q+2)/2,(p+q2)/2)f(x;p,q).f(Hc3(p+q+2)/2,(p+q2)/2)(3.3)0,?(Hc3(p+q+2)/2,(p+q2)/2)3.3.?x 3.3?,f(x;(p+q+2)/2,(p+q2)/2)f(x;p,q)=1/4(pq2)(2(pq)x3+(5p5q+4)x2+(pq)xp+q2)0.?,1/4(pq2)0,?x 3.3?,y(x)=2(pq)x3+(5p5q+4)x2+(pq)xp+q2 3.3,?y(3.3)=26.4+33.34(pq)0,?x3.3?,y(x)?,?y(3.3)=41.5621.724(pq)0.?y(x)0?pq=3,?PHc3(p+q+2)/2,(p+q2)/2)PHc3(p,q)0.引理8?n14,?(Hc2(n4)/2,(n4)/2)(Hc1(n4)/2,(n4)/2).证明?H(n42,n42)=(H(n42,n42),?n?H(n32,n52),?n?(5)PHc2(n4)/2,(n4)/2)PHc1(n4)/2,(n4)/2)=(x+1)n6(f1(n4)/2,(n4)/2)f2(n4)/2,(n4)/2).?1,2?,?n 14?n?,f(Hc1(q,s)(3.175)0,?(Hc1(q,s)0,?x3.175?,y(x)=8x3+(202n)x2+(286n)x+n43.175,?y(3.175)=142.935+6.7n0,?x3.175?,y(x)?,?y(3.175)=0.111 25n147.3350,?y(x)0.?,PHc2(n4)/2,(n4)/2)PHc1(n4)/2,(n4)/2).?n15?n?,f(Hc1(q,s)(3.175)0,?(Hc1(q,s)3.175.?x3.175?,f(Hc2(n3)/2,(n5)/2)f(Hc1(n3)/2,(n5)/2)=(x+1)n61/4(8n32)x3+(2n2+28n78)x2+(6n2+52n106)x+(n28n+15).?x3.175?,y(x)=(1/4)(8n32)x3+(2n2+28n78)x2+(6n2+52n106)x+(n28n+15)3.175,?y(3.175)=1.675n2+29.033 8n144.61 0,?x 3.175?,y(x)?,?y(3.175)=0.027 812 5n236.722 6n+147.363 0,?y(x)PHc1(n3)/2,(n5)/2).?,?n14?,(Hc2(n4)/2,(n4)/2)(Hc1(n4)/2,(n4)/2).引理9?n 13?,?(Hc2(n3)/2,(n5)/2)(Hc3(n1)/2,(n7)/2);?n 18?,?(Hc2(n4)/2,(n4)/2)(Hc3(n4)/2,(n6)/2).证明?2,?7?(5)?,?n 13?n?,PHc2(n3)/2,(n5)/2)PHc3(n1)/2,(n7)/2)=(x+1)n6(f(Hc2(n3)/2,(n5)/2)f(Hc3(n1)/2,(n7)/2)=(x+1)n6(n3)x3(1/2)(n11)n+16)x2+(1/4)(425n)n81)x+(1/4)(n8)n+7).?x 2.8?,y(x)=(n3)x3(1/2)(n11)n+16)x2+(1/4)(425n)n81)x+(1/4)(n8)n+7)2.8,?n5?,y(2.8)=1.55n2+3.22n46.010,?x2.8?,y(x)?,y(2.8)=0.17n210.232n+61.5860.?y(x)PHc3(n1)/2,(n7)/2).?n6?n?,?p+q 18?,PHc2(n4)/2,(n4)/2)PHc3(n4)/2,(n6)/2)=(x+1)n6f(Hc2(n4)/2,(n4)/2)f(Hc3(n4)/2,(n6)/2)=(x+1)n6(n4)x3(1/2)(n8)(n3)x2+(1/4)(425n)n88)x+(1/4)(n8)n+12).?x 3.3?,y(x)=(n4)x3(1/2)(n8)(n3)x2+(1/4)(425n)n88)x+(1/4)(n8)n+12)3.3,?n6?,y(3.3)=2.05n2+6.87n73.480,?x3.3?,y(x)?,?y(3.3)=1.07n212.692n+88.6680,?y(x)0,?PHc3(n4)/2,(n4)/2)PHc3(n4)/2,(n6)/2).?Hc Bcn,n4.?6 n 18?,?MATLAB?(Hc)(Hc2(n4)/2,(n4)/2).?n 19?,?8?9?(Hc)(Hc2(n4)/2,(n4)/2).?n=6?,(Hc2(1,1)=2(p2(64)2)/2=2.?n=7?,(Hc2(1,2)2.234 1(p2(74)2)/22.224 7.?,?n=7?,26?2024?(Hc)6?,g(p2(n4)2)/2)=(n5)2+1(n2)2n80,g(1)=4n0.?,Hc2(n4)/2,(n4)/2)?(p2(n4)2)/2.?n9?n?,?(5)?H2(n4)/2,(n4)/2)=H2(n3)/2,(n5)/2).?B=00100n520000n32n521000n3200000n32n520111n321n521101n32n521.?PHc2(n3)/2,(n5)/2)=(x+1)n6f(x;(n4)/2,(n4)/2),?f(x;(n4)/2,(n4)/2)=det(xEB)=(1/4)x(4x5+(244n)x4+(6416n)x3+(2n224n+54)x2+(3n212n7)x+40n4n292).?h(x)=4x5+(244n)x4+(6416n)x3+(2n224n+54)x2+(3n212n7)x+40n4n292,?n9?n?h(x)?(p2(n4)2)/2.?n9?,?h(p2(n4)2)/2),h(2.4)?h(1)?0?.?h(p2(n4)2)/2)=9n2n8/2 0,?n 9?h(2.4)?h(2.4)h(2.4)|n=9 26.083 84 0.?h(1)=5n2+40n75.?h(1)=10n+400,?n9?h(1)?h(1)h(1)|n=9=1200,?n9?h(0.851)?h(0.851)h(0.851)|n=11=0.069 3620.?h(n3)=2n4+31n3169n2+393n341,h(n3)=8n3+93n2338n+393,h(n3)=24n2+186n338?h(n3)=48n+1860.?h(n3)?h(n3)h(n3)|n=11=1 1960,?h(n3)?h(n3)h(n3)|n=11=2 7200,?h(n3)?h(n3)h(n3)|n=11=4 4880,h(n2)=8n3+9n2112n+129,h(n2)=24n2+18n112?h(n2)=48n+180.?h(n2)?h(n2)h(n2)|n=11=2 9840,?h(n2)?h(n2)h(n2)|n=11=10 5680,?h(n2)?h(n2)h(n2)|n=11=27 800 0.?n=9?,Hc2(94)/2,(94)/2)=Hc2(2,3).?(Hc2(2,3)2.574 5(p2(94)2)/22.581 1.?,?n8?,?HcBcn,n4?(Hc)(p2(n4)2)/2.参考文献：1JOHNSONC R?SAWIKOWSKA A?Minimizing the least eigenvalue of graphs with fixed order and sizeJ?Discrete Mathemat-ics?2012?312(15)?2272-2285?(下转第36页)36新疆大学学报（自然科学版）（中英文）2024年tencesC/Findings of the Association for Computational Linguistics：EMNLP 2020OnlineStroudsburg，PA，USA：Associationfor Computational Linguistics，2020：41-4623BIRD SNLTK：The natural language toolkitC/Proceedings of the COLING/ACL on Interactive Presentation SessionsACM，2006：69-7224YIN W P，SCHUTZE H，XIANG B，et alABCNN：Attention-based convolutional neural network for modeling sentencepairsJTransactions of the Association for Computational Linguistics，2016，4：259-27225YANG R Q，ZHANG J H，GAO X，et alSimple and effective text matching with richer alignment featuresC/Proceedings ofthe 57th Annual Meeting of the Association for Computational LinguisticsFlorence，ItalyStroudsburg，PA，USA：Associationfor Computational Linguistics，2019：4699-470926DEVLIN J，CHANG M W，LEE K，et alBERT：Pre-training of deep bidirectional transformers for language understand-ingEB/OL2018：arXiv：1810.04805https:/arxiv.org/abs/1810.04805.pdf27YANG Y，YIH W T，MEEK CWikiQA：A challenge dataset for open-domain question answeringC/Proceedings of the 2015Conference on Empirical Methods in Natural Language ProcessingLisbon，PortugalStroudsburg，PA，USA：Association forComputational Linguistics，2015：2013-201828WANG M Q，SMITH N A，MITAMURA TWhat is the Jeopardy model？A quasi-synchronous grammar for QAC/EMNLP-CoNLL 2007-Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and ComputationalNatural Language LearningJune 28-30，2007，Prague，Czech RepublicStroudsburg：ACL，2007：22-3229LIU T，WANG X，LYU C G，et alSentence matching with syntax-and semantics-aware BERTC/Proceedings of the 28th Inter-national Conference on Computational LinguisticsBarcelona，Spain(Online)Stroudsburg，PA，USA：International Committeeon Computational Linguistics，2020：3302-331230ZHANG Z S，WU Y W，ZHAO H，et alSemantics-aware BERT for language understandingJProceedings of the AAAIConference on Artificial Intelligence，2020，34(5)：9628-9635责任编辑：张自强(上接第26页)2LIU R F，ZHAI M Q，SHU J LThe least eigenvalue of unicyclic graphs with n vertices and k pendant verticesJLinear Algebraand Its Applications，2009，431(5/6/7)：657-6653YE M L，FAN Y Z，LIANG DThe least eigenvalue of graphs with given connectivityJLinear Algebra and Its Applica-tions，2009，430(4)：1375-13794FAN Y Z，ZHANG F F，WANG YThe least eigenvalue of the complements of treesJLinear Algebra and Its Applica-tions，2011，435(9)：2150-21555JIANG G S，YU G D，SUN W，et alThe least eigenvalue of graphs whose complements have only two pendent verticesJAppliedMathematics and Computation，2018，331：112-1196GUO J M，ZHANG G G，WANG Z W，et alThe least eigenvalue of unicyclic graphs with application to spectral spreadJAlgebraColloquium，2022，29(2)：265-2727LI S C，WANG S JThe least eigenvalue of the signless Laplacian of the complements of treesJLinear Algebra and ItsApplications，2012，436(7)：2398-24058LI Y J，QIN R，LI DOn distance signless Laplacian spectrum of the complements of unicyclic graphs and treesJLinearAlgebra and Its Applications，2021，631：235-2539卢志琴，马小玲 两种分裂点连接运算图的Randi c谱J 新疆大学学报(自然科学版)(中英文)，2022，39(5)：550-559LU Z Q，MA X LThe Randi c spectrum of two types of splitting-vertex join graphsJJournal of Xinjiang University(NaturalScience Edition in Chinese and English)，2022，39(5)：550-559(in Chinese)10QIN R，LI D，CHEN Y Y，et alThe distance eigenvalues of the complements of unicyclic graphsJLinear Algebra and ItsApplications，2020，598：49-6711HAEMERS W HInterlacing eigenvalues and graphsJLinear Algebra and Its Applications，1995，226/227/228：593-616责任编辑：赵新科