HAMILTON图的特征矩阵

THE CHARACTERISTIC MATRIX OF HAMILTONIAN GRAPH

讨论了Hamilton图G和它的邻接矩阵A之间的关系,得到如下结果定理1 图G是H—图当且仅当A=B+Q,这里B≥0且B≠0,Q=P CP,C是由互换单位矩阵中的第1行和第n行所得到的初等阵,P是置换阵,P是P的转置矩阵。定理2 图G是H—图当且仅当A的谱半径ρ(A)是A的单根,且存在正特征向量ξ,使得Aξ=ρ(A)ξ>η,这里η是由适当调整ξ的分量而得到的向量,满足:当ξ的第i个分量调为η的第j个分量时,A的(i,j)元a_(ij)=1。

In this paper, we discuss the relation between Hamiltonian graph and its adjacency matrix. The following results are proved: Theorem 1 A graph G is a Hamiltonian graph if and only if A=B+Q, where A denotes adjacency matrix of the graph G,B≥0 and B≠0,Q=P CP. C denotes the elementary matrix, which is obtained by exchanging the l-line (row) and the n-line(row) of a unit matrix. P denotes the permutation matrix. p^T denotes the transposed matrix of P. Theorem 2 A graph G is a Hamiltonian graph if and only if the spectral radius ρ(A) of the adjacency matrix A of the graph G is a single root of A. And there is a positive characteristic vector so that Aξ=ρ(A)ξ>η, where η denotes a positive vector, which is obtained by adjusting some coordinates of the vector ξ appropriately. It is satisfied as following: the (i,j)-element of A is equal to 1 as the i-coordinate of ξ adjusting to the j-coordinate of η.