可交换图的一些注记

doi:10.3785/j.issn.1008-9497.2024.02.005

浙江大学学报（理学版）

2024, Vol. 51

Issue (2): 172-177 DOI: 10.3785/j.issn.1008-9497.2024.02.005

数学与计算机科学

可交换图的一些注记

吴寒^1,²,刘奋进¹(

),尚凡琦^1,³,周艳红¹,阮昊桐¹

^1.长安大学理学院, 陕西西安 710064
^2.南京大学数学系, 江苏南京 210093
^3.哈尔滨工程大学青岛创新发展基地, 山东青岛 266000

A note on commutative graphs

Han WU^1,²,Fenjin LIU¹(

),Fanqi SHANG^1,³,Yanhong ZHOU¹,Haotong RUAN¹

^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

全文: PDF(687 KB)

HTML( 2 )

摘要：

如果存在一种顶点标号，使得2个简单图的邻接矩阵可交换，则称2个简单图可交换。首先，从图的Perron向量、主特征值数量、正则性三方面给出了可交换图的必要条件。然后，借助矩阵的克罗内克积、图的笛卡尔积及循环矩阵，构造了新的可交换图。最后，将一个邻接矩阵表示为另一个特征值互异的邻接矩阵的矩阵多项式，给出了2种算法，并比较了二者的优劣。可交换图存在公共的特征向量，对图谱理论研究具有重要意义。

关键词： 可交换图; 正则图; 循环图; 克罗内克积; 笛卡尔积

Abstract:

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.

Key words: commutative graph regular graph circulant graph Kronecker product Cartesian product

收稿日期: 2022-05-09 出版日期: 2024-03-08

CLC:

O 157.5

基金资助: 陕西省自然科学基础研究计划项目(2021JM-149);长安大学2020年大学生创新创业训练计划项目(S202010710247)

通讯作者: 刘奋进 E-mail: fenjinliu@chd.edu.cn

作者简介: 吴寒（2000—），ORCID：https：//orcid.org/0000-0002-4668-970X，女，本科生，主要从事图论及计算数学研究.

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	吴寒
	刘奋进
	尚凡琦
	周艳红
	阮昊桐

引用本文:

吴寒,刘奋进,尚凡琦,周艳红,阮昊桐. 可交换图的一些注记[J]. 浙江大学学报（理学版）, 2024, 51(2): 172-177.

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.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2024.02.005 或 https://www.zjujournals.com/sci/CN/Y2024/V51/I2/172

图1 主特征值数量不同的可交换图

图2 非正则可交换图G与G¯

图3 主特征值数量小于3的六阶连通图

图的序号	可交换图的序号
$G 6$	$G 6$
$G 7$	$G 7$ ， $G 13$
$G 8$	$G 8$
$G 9$	$G 9$ ， $G 17$ ， $G 19$ ， $G 20$
$G 10$	$G 10$ ， $G 16$
$G 11$	$G 11$
$G 12$	$G 12$
$G 13$	$G 7$ ， $G 13$
$G 14$	$G 14$
$G 15$	$G 15$
$G 16$	$G 10$ ， $G 16$
$G 17$	$G 9$ ， $G 17$ ， $G 19$ ， $G 20$
$G 18$	$G 18$
$G 19$	$G 9$ ， $G 17$ ， $G 19$
$G 20$	$G 9$ ， $G 17$ ， $G 20$
$G 21$	$G 21$
$G 22$	$G 22$
$G 23$	$G 23$

表1 主特征值数量为2的六阶连通图及与其对应的可交换连通图

图4 一对可互相表示为其邻接矩阵的矩阵多项式的可交换图

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.

[1]	周后卿. 几类整循环图的秩的界[J]. 浙江大学学报（理学版）, 2020, 47(3): 301-305.
[2]	周后卿. 循环图的预解Estrada指标[J]. 浙江大学学报（理学版）, 2016, 43(5): 517-520.

Viewed

Full text

Abstract

Cited

Shared

Discussed