剩余类图的代数特性：特征多项式与邻接矩阵

"这篇论文是2011年发表在《山西大学学报(自然科学版)》上的，作者是徐高奎和刘博，主要探讨了整数的剩余类图的代数性质，特别是当剩余类图的色数为2或3时，其邻接矩阵对应的特征多项式的形式。" 在图论中，剩余类图是一种特殊的图，它基于整数的除法关系。给定一个正整数n，剩余类图G的顶点集合由0到n-1的整数组成，两个顶点u和v之间有边相连当且仅当u和v在模n意义下是不相等的。这种图在数论和图论的交叉领域中有重要应用，因为它能直观地展示整数模n的关系。 定义中提到了几个关键概念： 1. 完全图：图G的所有顶点间都有边连接，其邻接矩阵对角线外的所有元素都是1。 2. 邻接矩阵：表示图G中顶点之间的连接情况，矩阵元素a_ij=1表示顶点i和j之间有边，否则为0。 3. 正常着色（或称色数）：图G的正常着色是指使用最少的颜色使相邻顶点颜色不同，色数χ(G)是使用的最小颜色数。 4. 剩余类图：顶点为0到n-1的整数，边连接的是那些模n等价的整数对。 论文利用行列式的性质，即邻接矩阵的特征多项式，来研究剩余类图的特性。特征多项式是描述矩阵特征值的代数表达式，对于图的邻接矩阵，它与图的谱理论密切相关，包括色数、连通性等图的性质。 引理1指出，完全图的色数等于其顶点数，这是因为要使得所有顶点颜色不同，至少需要n种颜色。引理2则表明，在剩余类图中，两个顶点相邻当且仅当它们的模n余数是互素的，这直接来源于欧几里得算法和最大公约数的性质。 文章的核心贡献在于揭示了当剩余类图的色数为2或3时，其特征多项式具有的具体形式。这对于理解这些图的结构和性质具有重要意义，同时可能为解决更复杂的问题提供基础，如寻找更有效的着色策略或优化算法。 由于篇幅限制，具体特征多项式的表达式和推导过程未能在此详述，但可以想象，这样的结果可能涉及到高斯消元、多项式根的性质以及整数的整除性等数学工具。这些结果对于图论、代数学以及计算理论的研究者来说都是有价值的发现。