Han WU1,2,Fenjin LIU1(),Fanqi SHANG1,3,Yanhong ZHOU1,Haotong RUAN1
1.School of Science,Chang'an University,Xi'an 710064,China 2.Department of Mathematics,Nanjing University,Nanjing 210093,China 3.Qingdao Innovation and Development Base of Harbin Engineering University,Qingdao 266000,Shandong Province,China
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.
Han WU,Fenjin LIU,Fanqi SHANG,Yanhong ZHOU,Haotong RUAN. A note on commutative graphs. Journal of Zhejiang University (Science Edition), 2024, 51(2): 172-177.
Fig.1 Commutative graphs with different number of main eigenvalues
Fig.2 Non-regular commutative graphs and
Fig.3 Connected graphs with 6 vertices and the number of main eigenvalues less than 3
图的序号
可交换图的序号
,
,,,
,
,
,
,,,
,,
,,
Table 1Connected graphs with six vertices two main eigenvalues and their commutative graphs
Fig.4 A pair of commutative graphs that can be expressed as matrix polynomial of their adjacency matrices
[1]
HORN R A, JOHNSON C R. Matrix Analysis[M]. 2nd ed. Cambridge / New York: Cambridge University Press, 2012.
[2]
GODSIL C D, MCKAY B D. Constructing cospectral graphs[J]. Aequationes Mathematicae, 1982, 25(1): 257-268. DOI: 10.1007/BF02189621
doi: 10.1007/BF02189621
[3]
LIU F J, WANG W, YU T, et al. Generalized cospectral graphs with and without Hamiltonian cycles[J]. Linear Algebra and Its Applications, 2020, 585: 199-208. DOI: 10.1016/j.laa.2019.10.001
doi: 10.1016/j.laa.2019.10.001
[4]
JI Y Z, GONG S C, WANG W. Constructing cospectral bipartite graphs[J]. Discrete Mathematics, 2020, 343(10): 112020. DOI: 10.1016/j.disc.2020.112020
doi: 10.1016/j.disc.2020.112020
[5]
HEINZE A. Applications of Schur Rings in Algebraic Combinatorics: Graphs, Partial Difference Sets and Cyclotomic Schemes[D]. Oldenburg: Universität Oldenburg, 2001.
[6]
BEEZER R A. On the polynomial of a path[J]. Linear Algebra and Its Applications, 1984, 63: 221-225. DOI: 10.1016/0024-3795(84)90144-7
doi: 10.1016/0024-3795(84)90144-7
[7]
AKBARI S, MOAZAMI F, MOHAMMADIAN A. Commutativity of the adjacency matrices of graphs[J]. Discrete Mathematics, 2009, 309(3): 595-600. DOI: 10.1016/j.disc.2008.09.006
doi: 10.1016/j.disc.2008.09.006
[8]
COLLINS L, SCIRIHA I. The walks and CDC of graphs with the same main eigenspace[J]. Discussiones Mathematicae Graph Theory, 2023, 43 (2): 507-532. DOI: 10.7151/dmgt.2386
doi: 10.7151/dmgt.2386
[9]
GODSIL C, ROYLE G. Algebraic Graph Theory[M]. New York: Springer, 2001. doi:10.1007/978-1-4613-0163-9
doi: 10.1007/978-1-4613-0163-9
[10]
CVETKOVIĆ D M, ROWLINSON P. An Introduction to the Theory of Graph Spectra: 48[M]. Cambridge: Cambridge University Press, 2010. doi:10.1017/cbo9780511801518
doi: 10.1017/cbo9780511801518
[11]
高随祥. 图论与网络流理论[M]. 北京: 高等教育出版社, 2009. GAO S X. Graph Theory and Network Flow Theory[M]. Beijing: Higher Education Press, 2009.
[12]
丘维声. 高等代数(下册)[M]. 北京: 清华大学出版社, 2019. QIU W S. Higher Algebra (Vol 2)[M]. Beijing: Tsinghua University Press, 2019.