Golden Laplacian Graphs

Overview & Synopsis

The Laplacian spectra of graphs 0 = µ 1 < µ 2 ≤ • • • ≤ µn play fundamental roles in understanding the structure of connected graphs and of dynamics taking place on them. Here, we dene golden Laplacian graphs (GLG) as those for which the ratio between the length of the spectrum µn-µ 1 and its spread µn-µ 2 is identical to that between the spread and µ 2-µ 1. This happens when the ratios are identical to the golden ratio φ = 1 + √ 5 /2. We prove here (i) the existence of GLG, (ii) nd all of them with n ≤ 10 vertices, (iii) prove a few of their graph-theoretic and algebraic properties and (iv) nd methods to expand them to bigger sizes. More importantly, we prove here that GLG are extremely robust graphs, i.e., they have large vertex and edge connectivity, and large isoperimetric constant, and are among the top synchronizable ones for graphs of the same size. Therefore, GLG are very good candidates for communication networks.