A Note on Eigenvalues and Asymmetric Graphs

被引:0
作者
Lotfi, Abdullah [1 ]
Mowshowitz, Abbe [2 ]
Dehmer, Matthias [3 ,4 ,5 ]
机构
[1] Shahid Rajaee Teacher Training Univ, Fac Sci, Dept Math, Tehran 16785136, Iran
[2] CUNY City Coll, Dept Comp Sci, 138th St & Convent Ave, New York, NY 10031 USA
[3] Swiss Distance Univ Appl Sci, Dept Comp Sci, Schinerstr 18,Postfach 689, CH-3900 Brig, Switzerland
[4] Tyrolean Private Univ UMIT TIROL, Dept Biomed Comp Sci & Mechatron, A-6060 Hall In Tirol, Austria
[5] Nankai Univ, Coll Artificial Intelligence, Tianjin 300350, Peoples R China
关键词
automorphism group; eigenvalue; eigenvector; identity graph; asymmetric graph; Google matrix; Laplacian matrix;
D O I
10.3390/axioms12060510
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
This note is intended as a contribution to the study of quantitative measures of graphcomplexity that use entropy measures based on symmetry. Determining orbit sizes of graph automorphismgroups is a key part of such studies. Here we focus on an extreme case where every orbitcontains just a single vertex. A permutation of the vertices of a graph G is an automorphism if, andonly if, the corresponding permutation matrix commutes with the adjacency matrix of G. This factestablishes a direct connection between the adjacency matrix and the automorphism group. In particular,it is known that if the eigenvalues of the adjacency matrix of G are all distinct, every non-trivialautomorphism has order 2. In this note, we add a condition to the case of distinct eigenvalues thatmakes the graph asymmetric, i.e., reduces the automorphism group to the identity alone. In addition,we prove analogous results for the Google and Laplacian matrices. The condition is used to buildan O(n(3)) algorithm for detecting identity graphs, and examples are given to demonstrate that it issufficient, but not necessary.
引用
收藏
页数:13
相关论文
共 50 条
  • [31] On edge-path eigenvalues of graphs
    Akbari, Saieed
    Azizi, Seyran
    Ghorbani, Modjtaba
    Li, Xueliang
    LINEAR & MULTILINEAR ALGEBRA, 2022, 70 (15) : 2998 - 3008
  • [32] ON REGULAR SIGNED GRAPHS WITH THREE EIGENVALUES
    Andelic, Milica
    Koledin, Tamara
    Stanic, Zoran
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2020, 40 (02) : 405 - 416
  • [33] A note on eigenvalues of perturbed Hermitian matrices
    Li, CK
    Li, RC
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 395 : 183 - 190
  • [34] Edge-Disjoint Spanning Trees, Edge Connectivity, and Eigenvalues in Graphs
    Gu, Xiaofeng
    Lai, Hong-Jian
    Li, Ping
    Yao, Senmei
    JOURNAL OF GRAPH THEORY, 2016, 81 (01) : 16 - 29
  • [35] NOTE ON BOUNDS FOR EIGENVALUES USING TRACES
    Sharma, R.
    Pal, M.
    OPERATORS AND MATRICES, 2022, 16 (03): : 759 - 773
  • [36] The effect on eigenvalues of connected graphs by adding edges
    Guo, Ji-Ming
    Tong, Pan-Pan
    Li, Jianxi
    Shiu, Wai Chee
    Wang, Zhi-Wen
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2018, 548 : 57 - 65
  • [37] On the bounds for the largest Laplacian eigenvalues of weighted graphs
    Sorgun, Sezer
    Buyukkose, Serife
    DISCRETE OPTIMIZATION, 2012, 9 (02) : 122 - 129
  • [38] Graphs with n-1 main eigenvalues
    Du, Zenan
    Liu, Fenjin
    Liu, Shunyi
    Qin, Zhongmei
    DISCRETE MATHEMATICS, 2021, 344 (07)
  • [39] Eigenvalues of the discrete p-Laplacian for graphs
    Amghibech, S
    ARS COMBINATORIA, 2003, 67 : 283 - 302
  • [40] Induced subgraph and eigenvalues of some signed graphs
    Hu, Fu-Tao
    Sun, Mei-Yu
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2022, 19 (03) : 167 - 170