On the Main Eigenvalues of Universal Adjacency Matrices and U-Controllable Graphs

Abstract

A universal adjacency matrix U of a graph G is a linear combination of the 0â1 adjacency matrix A, the diagonal matrix of vertex degrees D, the identity matrix I and the matrix J each of whose entries is 1. A main eigenvalue of U is an eigenvalue having an eigenvector that is not orthogonal to the allâones vector. It is shown that the number of distinct main eigenvalues of U associated with a simple graph G is at most the number of orbits of any automorphism of G. The definition of a Uâcontrollable graph is given using controlâtheoretic techniques and several necessary and sufficient conditions for a graph to be Uâcontrollable are determined. It is then demonstrated that Uâcontrollable graphs are asymmetric and that the converse is false, showing that there exist both regular and nonâregular asymmetric graphs that are not Uâcontrollable for any universal adjacency matrix U. To aid in the discovery of these counterexamples, a gammaâLaplacian matrix L(gamma) is used, which is a simplified form of U. It is proved that any U-controllable graph is a L(gamma)âcontrollable graph for some parameter gamma.