邻接矩阵在简单多项式中的实现

Simple Polynomial Generation of Adjacency Matrices

摘要: 在代数图论中，邻接矩阵的多项式变换为刻画图特征子空间及对称性之间的联系提供了重要工具。本文研究简单无向图的邻接矩阵经特定3次及以下多项式变换前后仍保持图的邻接性的问题，系统刻画了满足该性质的图类。通过对二次与三次多项式的分类讨论，给出了邻接矩阵经多项式变换后仍对应邻接矩阵的必要条件，证明其必须为正则图且不含特定圈C₄作为子图。在此基础上，分析了广义彼得森图$P\left(n,k\right)$ ，确定了其在一类3次多项式变换下保持邻接矩阵性质的参数约束。进一步，本文刻画了多项式$x^2-k$ 变换前后保持同构的图，证明满足上述条件的图只有奇圈。最后，讨论了两类特殊图，彼德森图$P\left(5,2\right)$ 和树$W_n$ ，找出了两个三次多项式，使其邻接矩阵在变换后仍对应某个图。

Abstract: In algebraic graph theory, polynomial transformations of adjacency matrices provide an important tool for characterizing the relationship between graph eigenspaces and symmetry. This paper investigates the problem of preserving graph adjacency when the adjacency matrix of a simple undirected graph undergoes specific polynomial transformations of degree 3 or lower, and systematically characterizes the classes of graphs satisfying this property. Through the classification and discussion of quadratic and cubic polynomials, the necessary conditions for the adjacency matrix to still correspond to an adjacency matrix after polynomial transformation are given, proving that it must be a regular graph and contain no specific cycles as subgraphs. On this basis, the generalized Petersen graph $P\left(n,k\right)$ is analyzed, and the parameter constraints for preserving the adjacency matrix property under a class of cubic polynomial transformations are determined. Furthermore, this paper characterizes graphs that remain isomorphim before and after polynomial $x^2-k$ transformation, proving that the only graphs satisfying the above conditions are odd cycles. Finally, two special types of graphs, the Petersen graph $P\left(5,2\right)$ and trees $W_n$ , are discussed, and two cubic polynomials are found such that their adjacency matrices still correspond to some graph after transformation.