给定最大度的补图的最小特征值  

The Least Eigenvalue of the Complements of Graphs with Given Maximum Degree

作　　者：王东宜 

机构地区：[1]新疆师范大学数学科学学院,新疆 乌鲁木齐

出　　处：《理论数学》2024年第6期9-14,共6页Pure Mathematics

摘　　要：假设G是一个简单连通图,其顶点集V(G)={v1,v2,⋯,vn}。图G的邻接矩阵表示为A(G)=(aij)n×n,其中如果两个顶点vi和vj在图G中相邻,则aij=1;否则aij=0。用Jn表示所有元素均为1的n阶矩阵,并且用In表示n阶单位矩阵,那么A(Gc)和A(G)之间有A(Gc)=Jn−In−A(G)。在这篇文章中,通过使用A(Gc)和A(G)的关系,确定了给定最大度Δ≥⌈n2⌉的所有简单图的补图中最小特征值达到最小的图。Suppose G is a connected simple graph with the vertex setV(G)={v1,v2,⋯,vn}. The adjacency matrix of G isA(G)=(aij)n×n, whereaij=1if two verticesviandvjare adjacent in G andaij=0otherwise. LetJnbe the matrix of order n whose all entries are 1 andInbe the identity matrix of order n. Then we haveA(Gc)=Jn−In−A(G). In this paper using the relationship betweenA(Gc)andA(G), we determine the graphs whose least eigenvalue is minimum among all complements of graphs with given maximum degreeΔ≥⌈n2⌉.

关 键 词：最小特征值 最大度 补图 

分 类 号：O15[理学—数学]