16471 - Algebraic properties of regular graphs. (with I. Pitault)

N. Lygeros, I. Pitault

A nice result, in Spectral Graph Theory, due to Cvetković, Doob and Sachs, is a characterization of regular graphs in their adjacency matrices. A regular graph is a graph where every vertex has the same degree. For example, Platonic Graphs are regular graphs. They correspond to the skeleton of a Platonic solid. The regularity of Platonic Graphs is cubic for tetrahedral, cubical and dodecahedral graph, quartic for octahedral graph and finally quintic for icosahedral graph. Even for the 13 Archimedean graphs, which correspond to the skeleton of the Archimedean solids, the regularity is cubic, quantic or quintic. With the global characterization of CDS, we get of course a result with Platonic and Archimedean Graphs. Let consider A, the adjacency matrix of a graph. The graph is regular if and only if the vector (1, …, 1) is an eigenvector of A. It is interesting to notice that this theorem can be generalized for Laplacian Theory and signless Laplacian Theory. This has been done by Cvetković and Simić. In fact, the whole theory of spectra of the adjacency matrix and of the Laplacian matrix for regular graphs, has a direct equivalent in signless Laplacian Theory. It is sufficient to observe that for a regular graph of degree r, as we have D=rI and A=Q-rI, we have PG(x)=QG(x+r). So the mapping φ(q)=q-r maps the Q-eigenvalues to the A-eigenvalues. In fact, we have an isomorphism, in this special case, between the A-theory and the Q- theory. CDS proved also that a regular graph of degree k is connected if and only if the eigenvalue K has multiplicity one. Since Platonic and Archimedean graphs are of course connected we have also this proprierty. By the way, we know also that the eigenvalue of the eigenvector (1, …, 1) is the degree of the graph since it is constant. And the eigenvectors corresponding to other eigenvalues are orthogonal to (1, …, 1) so for such eigenvectors the sum of their coordinates is null.