Cette note a pour but de démontrer de manière élémentaire un résultat de théorie spectrale des graphes et d’étudier les conséquences de celui-ci sur les graphes d’objets réguliers, périodiques, quasi-périodique ou irréguliers.

Théorème : Le rayon spectral de la matrice d’adjacence d’un graphe simple est inférieur ou égal au degré maximal des sommets.

Démonstration : Considérons la matrice d’adjacence d’un graphe simple. Par définition, le rayon spectral est la valeur maximale des modules des valeurs propres de la matrice or ce dernier, dans le cas général, est inférieur ou égal à toute norme de la matrice. Par construction, les matrices d’adjacence sont nécessairement symétriques et donc hermitiennes, aussi le rayon spectral est égal à la valeur de la norme ||.||_2. Tout autre norme a une valeur nécessairement plus grande puisque le rayon spectral correspond à la borne inférieure. Considérons les normes ||.||_1 et ||.||_infini. La norme ||.||_1 correspond au maximum des sommes des colonnes de la matrice et la norme ||.||_infini correspond au maximum des sommes des lignes de la matrice associée. Dans le cas d’une matrice d’adjacence, ces deux normes sont égales. Comme la somme des lignes ou des colonnes, représente le degré d’un sommet du graphe, nous en déduisons que ces normes sont en réalité le degré maximal des sommets et donc du graphe, ce qu’il fallait démontrer.

Remarque : Le résultat reste valable pour la matrice laplacienne du graphe simple.

Applications à des objets réguliers : Examinons à présent, deux applications de notre résultat spectral élémentaire sur des objets réguliers. Considérons deux cubes avec une face commune alors nous avons : d_max=4 donc vp_max
Application à un objet quasi-périodique : Considérons le pavage de Penrose. Les degrés possibles dans ce dernier sont d’ordre 3, 4, 5, 6 et 7. Nous en déduisons que le module de la valeur propre maximale du polynôme caractéristique d’une région bornée du pavage de Penrose, est inférieur ou égal à 7.

Application à un objet irrégulier : Considérons le cas d’une famille d’objets croissants en termes de sommets dont le degré maximal des sommets est de petite taille par rapport au nombre de sommets et dont le polynôme caractéristique de la matrice d’adjacence est scindé dans les nombres réels i.e. toutes ses valeurs propres sont réelles et de multiplicité un. Dans ce cas, les spectres des graphes associés seront bornés par une borne de petite taille.