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

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

摘要: 假设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⌉的所有简单图的补图中最小特征值达到最小的图。

Abstract: 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⌉.