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）A note on commutative graphs(可交换图的一些注记)
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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Zhejiang University Press
2024-03-01
|
| Series: | Zhejiang Daxue xuebao. Lixue ban |
| Subjects: | |
| Online Access: | https://doi.org/10.3785/j.issn.1008-9497.2024.02.005 |
| _version_ | 1797230874409828352 |
|---|---|
| author | 吴寒(WU Han) 刘奋进(LIU Fenjin) 尚凡琦(SHANG Fanqi) 周艳红(ZHOU Yanhong) 阮昊桐(RUAN Haotong) |
| author_facet | 吴寒(WU Han) 刘奋进(LIU Fenjin) 尚凡琦(SHANG Fanqi) 周艳红(ZHOU Yanhong) 阮昊桐(RUAN Haotong) |
| author_sort | 吴寒(WU Han) |
| collection | DOAJ |
| description | 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.(如果存在一种顶点标号，使得2个简单图的邻接矩阵可交换，则称2个简单图可交换。首先，从图的Perron向量、主特征值数量、正则性三方面给出了可交换图的必要条件。然后，借助矩阵的克罗内克积、图的笛卡尔积及循环矩阵，构造了新的可交换图。最后，将一个邻接矩阵表示为另一个特征值互异的邻接矩阵的矩阵多项式，给出了2种算法，并比较了二者的优劣。可交换图存在公共的特征向量，对图谱理论研究具有重要意义。) |
| first_indexed | 2024-04-24T15:35:25Z |
| format | Article |
| id | doaj.art-8d1b361ff3e548dc80ad58585243b811 |
| institution | Directory Open Access Journal |
| issn | 1008-9497 |
| language | zho |
| last_indexed | 2024-04-24T15:35:25Z |
| publishDate | 2024-03-01 |
| publisher | Zhejiang University Press |
| record_format | Article |
| series | Zhejiang Daxue xuebao. Lixue ban |
| spelling | doaj.art-8d1b361ff3e548dc80ad58585243b8112024-04-02T02:09:53ZzhoZhejiang University PressZhejiang Daxue xuebao. Lixue ban1008-94972024-03-0151217217710.3785/j.issn.1008-9497.2024.02.0051. 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）A note on commutative graphs(可交换图的一些注记)吴寒(WU Han)0https://orcid.org/0000-0002-4668-970X刘奋进(LIU Fenjin)1https://orcid.org/0000-0001-8759-7695尚凡琦(SHANG Fanqi)2周艳红(ZHOU Yanhong)3阮昊桐(RUAN Haotong)4(1长安大学 理学院,陕西 西安 710064)(1长安大学 理学院,陕西 西安 710064)(1长安大学 理学院,陕西 西安 710064)(1长安大学 理学院,陕西 西安 710064)(1长安大学 理学院,陕西 西安 710064)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.(如果存在一种顶点标号，使得2个简单图的邻接矩阵可交换，则称2个简单图可交换。首先，从图的Perron向量、主特征值数量、正则性三方面给出了可交换图的必要条件。然后，借助矩阵的克罗内克积、图的笛卡尔积及循环矩阵，构造了新的可交换图。最后，将一个邻接矩阵表示为另一个特征值互异的邻接矩阵的矩阵多项式，给出了2种算法，并比较了二者的优劣。可交换图存在公共的特征向量，对图谱理论研究具有重要意义。)https://doi.org/10.3785/j.issn.1008-9497.2024.02.005commutative graph(可交换图)regular graph(正则图)circulant graph(循环图)kronecker product(克罗内克积)cartesian product(笛卡尔积) |
| spellingShingle | 吴寒(WU Han) 刘奋进(LIU Fenjin) 尚凡琦(SHANG Fanqi) 周艳红(ZHOU Yanhong) 阮昊桐(RUAN Haotong) 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）A note on commutative graphs(可交换图的一些注记) Zhejiang Daxue xuebao. Lixue ban commutative graph(可交换图) regular graph(正则图) circulant graph(循环图) kronecker product(克罗内克积) cartesian product(笛卡尔积) |
| title | 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）A note on commutative graphs(可交换图的一些注记) |
| title_full | 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）A note on commutative graphs(可交换图的一些注记) |
| title_fullStr | 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）A note on commutative graphs(可交换图的一些注记) |
| title_full_unstemmed | 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）A note on commutative graphs(可交换图的一些注记) |
| title_short | 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）A note on commutative graphs(可交换图的一些注记) |
| title_sort | 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 a note on commutative graphs 可交换图的一些注记 |
| topic | commutative graph(可交换图) regular graph(正则图) circulant graph(循环图) kronecker product(克罗内克积) cartesian product(笛卡尔积) |
| url | https://doi.org/10.3785/j.issn.1008-9497.2024.02.005 |
| work_keys_str_mv | AT wúhánwuhan 1schoolofsciencechanganuniversityxian710064china2departmentofmathematicsnanjinguniversitynanjing210093china3qingdaoinnovationanddevelopmentbaseofharbinengineeringuniversityqingdao266000shandongprovincechinaanoteoncommutativegraphskějiāohuàntúdeyīxiēzhùjì AT liúfènjìnliufenjin 1schoolofsciencechanganuniversityxian710064china2departmentofmathematicsnanjinguniversitynanjing210093china3qingdaoinnovationanddevelopmentbaseofharbinengineeringuniversityqingdao266000shandongprovincechinaanoteoncommutativegraphskějiāohuàntúdeyīxiēzhùjì AT shàngfánqíshangfanqi 1schoolofsciencechanganuniversityxian710064china2departmentofmathematicsnanjinguniversitynanjing210093china3qingdaoinnovationanddevelopmentbaseofharbinengineeringuniversityqingdao266000shandongprovincechinaanoteoncommutativegraphskějiāohuàntúdeyīxiēzhùjì AT zhōuyànhóngzhouyanhong 1schoolofsciencechanganuniversityxian710064china2departmentofmathematicsnanjinguniversitynanjing210093china3qingdaoinnovationanddevelopmentbaseofharbinengineeringuniversityqingdao266000shandongprovincechinaanoteoncommutativegraphskějiāohuàntúdeyīxiēzhùjì AT ruǎnhàotóngruanhaotong 1schoolofsciencechanganuniversityxian710064china2departmentofmathematicsnanjinguniversitynanjing210093china3qingdaoinnovationanddevelopmentbaseofharbinengineeringuniversityqingdao266000shandongprovincechinaanoteoncommutativegraphskějiāohuàntúdeyīxiēzhùjì |