可交换图的一些注记OA北大核心CSTPCD

Two simple graphs are commutative if there exists a labelling of their vertices such that their adjacency matrices can commute.This paper gives three necessary conditions ensuring the commutativity of certain graphs from Perron vectors,the number of main eigenvalues,the regularity of graphs.Then we construct new commutative graphs by graph Kronecker product,Cartesian product and circulant matrix.Finally,for two commutative graphs,we provide two algorithms that can express one adjacency matrix as the matrix polynomial of another adjacency matrix with distinct eigenvalues,and compare their merits.Commutative graphs sharing common eigenvectors are essential to the study of spectral graph theory.