# Study of the Spectrum of a Cayley Graph

Nestor Anzola, Kibamba Ab, Kuya Biaba, Ngentshi Benoît, Frey Sylvestre

► To cite this version:

Nestor Anzola, Kibamba Ab, Kuya Biaba, Ngentshi Benoît, Frey Sylvestre. Study of the Spectrum of a Cayley Graph. Revue Internationale de la Recherche Scientifique, In press, 10.5281/zenodo.14021898 .
hal-04769495

HAL Id: hal-04769495

https://hal.science/hal-04769495v1

Submitted on 6 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
<figure><img src="image_1.png" /></figure>

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

# Etude de spectre de graphe de Cayley

Nestor Anzola Kibamba<sup>ab, b, c</sup>, Biaba Kuya Jirince<sup>a, b, c</sup>, Mpongo Ngentshi Benoît<sup>a, b</sup>, Frey Sylvestre<sup>a, b, d</sup>

## Abstract:

* The regularity of a directed graph provides us with an eigenvalue that turns out to be the largest in magnitude for such a graph;

* We will also define the notion of a path in a graph to study its connectivity;

* The most interesting point in this work is the concept of the adjacency matrix of a finite regular graph, which will allow us to explore the relationship between the graph's connectivity and the eigenvalues of the matrix;

* We will conclude this work with a method for calculating the eigenvalues of Cayley graphs defined from abelian groups. To this end, we will recall some results from representation theory.

**Keywords:** graphe orienté, graphe régulier, graphe k-partites, matrice d'adjacence, graphe connexe, chemin, spectre d'un graphe, graphe de Cayley, valeurs propres, groupe abélien.

**Digital Object Identifier (DOI):** https://doi.org/10.5281/zenodo.14021898

## 1 Introduction

Un des plus anciens problèmes combinatoires, est la détermination d'un itinéraire à travers la ville de Königsberg (aujourd'hui Kaliningrad) en utilisant qu'une fois et une seule chacun des sept ponts qui enjambaient les bras de la rivière où conduisaient à deux îles, dont Euler montra en 1735 l'impossibilité en utilisant un argument simple, de parité, semble constituer le premier témoignage de l'emploi des graphes :

<footnote><sup>a</sup> University of Kinshasa (UNIKIN), Democratic Republic of Congo.</footnote>

<footnote><sup>b</sup> Faculty of Science and Technology, B.P. 190 Kinshasa XI, University of Kinshasa (UNIKIN), Democratic Republic of Congo.</footnote>

<footnote><sup>c</sup> Institut Francophone International (IFI)/Vietnam National University Hanoi, adresse 144 Xuan Thuy, Cau Giay, Hanoi, Vietnam</footnote>

<footnote><sup>d</sup> Forest Management Technique, Regional Postgraduate School of Integrated Management and Management of Forests and Tropical Territories (ÉRAIFT) Commune of Lemba - P.O. Box 15.373, University of Kinshasa, Commune of Lemba, B.P. 15.373, Democratic Republic of Congo.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 1. 7 ponts et graphe associé</figcaption></figure>

Plus tard, J. Petersen, avec ses graphes réguliers (1891), André Sainte-Laguë, ancien professeur du CNAM, avec la première thèse sur les réseaux (ou graphes), en 1926, et surtout Dénes König, publiant sa théorie der endlichen und unendlichen Graphen (1936), développèrent ce concept. C'est en 1958 que Claude Berge fait paraître sa théorie des graphes et applications, considérablement amplifiée dans Graphes et hypergraphes (1971), d'où un renouvellement, un essor des recherches, notamment en France, en Hongrie, aux États-Unis, en Union Soviétique (aujourd'hui Russie) et au japon.

La théorie des graphes est devenue l'un des instruments les plus efficaces pour représenter (modéliser), puis résoudre de nombreux problèmes discrets que pose la recherche opérationnelle. Claude Berge a reconnu que la R.O. contribue aux progrès de la théorie des graphes, en suscitant de nouvelles recherches.

Grâce à ses nombreuses applications dans divers domaines scientifiques comme les mathématiques (optimisation combinatoire, probabilité, algèbre,...), l'informatique (algorithmique, bases de données, réseau,...) ou encore dans l'étude de la génétique, la théorie des graphes est aujourd'hui beaucoup étudiée.

## Léonard Euler ayant été le premier à proposer un traitement mathématique du problème, l'origine de la théorie des graphes lui fut accordée.

La théorie des graphes se penche sur l'étude de telles structures: différentes propriétés peuvent être étudiées. D'une part, une matrice peut être associée à chaque graphe: la matrice d'adjacence. Les valeurs propres de cette matrice constituent l'ensemble des valeurs propres du graphe. Cet ensemble est appelé spectre. D'autre part, une propriété d'expansion peut être associée à un graphe. Celle-ci mesure la connexité du graphe, c'est-à-dire si ses nœuds sont fortement reliés entre eux ou non.

Généralement ce travail a pour objectif l'étude des valeurs propres d'un graphe c'est-à-dire le spectre des graphes. Pour ce faire, nous allons introduire, dans un premier temps, les concepts nécessaire pour définir ces valeurs propres. Dans un second temps, nous étudierons ces dernières dans le cadre particulier du graphe de Cayley.

# 2 Généralités sur le graphe

## 2.1 Définitions

### 2.1.1 Définition 1

Un graphe $r$ est constitué d'un ensemble de nœuds $V$, d'un ensemble d'arêtes $E$ et d'une fonction d'incidence :

$$ \varphi: E \to V \times V \to (0(y), t(y)) \qquad (1) $$

Les nœuds $0(y)$ et $t(y)$ sont respectivement appelés l'origine et la destination de l'arête $y$ et cette dernière est dite orientée de $0(y)$ vers $t(y)$. Souvent, l'usage veut que l'on note simplement $r = (V, E)$.
## 2.1.2 Définition 2

Soient un graphe $r = (V, E)$ et $y, y' \in E$ deux arêtes possédant la propriété :

$$ (0(y), t(y))=(t(y')), 0((y')) \quad (2) $$

L'ensemble $\{y, y'\}$ est appelé arête géométrique ou encore arête non-orientée et les arêtes $y$ et $y'$ sont dans ce cas appelées arêtes opposées. Les nœuds $0(y)$ et $t(y)$ sont les extrémités de l'arête géométrique. Dans le cas où l'origine et la destination d'une arête coïncident, cette dernière est appelée une boucle et elle constitue à elle seule (par convention) une arête géométrique. Par la suite, le cardinal d'un ensemble E sera noté $|E|$.

## 2.1.3 Définition 3

### Multiplicité d'une paire

Soient $r = (V, E)$ un graphe et $i, j$ deux nœuds.

a. Notons par $m^+(i, j)$= le nombre d'arêtes ayant $i$ comme origine et $j$ comme destination

b. Notons aussi par $m^-(i, j)$= le nombre d'arêtes ayant $i$ comme destination et $j$ comme origine.

c. Notons par $m(i, j)= m^+(i, j) + m^-(i, j)$, (2) la multiplicité de la paire $(i, j)$.

## 2.1.4 Définition 4

### Degré d'un sommet

Soient $r = (V, E)$ un graphe et $i \in V$

Notons par $d^+(i) = \text{le demi-degré extérieur de } i \text{ c'est-à-dire le nombre d'arêtes ayant } i \text{ comme origine et par } d^-(i) = \text{le demi-degré intérieur de } i \text{ c'est-à-dire le nombre d'arêtes ayant } i \text{ comme destination.}$

Notons par $d(i) = d^+(i)+ d^-(i)$ (3) c'est-à-dire le degré de $i$ ou encore le nombre d'arêtes ayant $i$ comme extrémité.

Un graphe $r$ sera dit non-orienté s'il ne possède que des arêtes géométriques, ce qui se traduit formellement de la manière suivante :

## 2.1.5 Définition 5

Un graphe $r = (V, E)$ est non-orienté si pour tout couple de nœuds $(a, b) \in V \times V$,

$$ |\{y \in E | \varphi(y) = (a; b)\}| = |\{y \in E | \varphi(y) = (a, b)\}| \quad (3) $$

Ou encore

$$ m^+(a, b) = m^-(a, b) \quad (4) $$

Un graphe sera dit simplement non-orienté s'il est non-orienté et s'il possède au plus une arête géométrique entre chaque couple de nœuds.

De la même manière, un graphe est dit orienté s'il ne possède que des arêtes orientées, ce qui revient à dire que les seules arêtes géométriques sont des boucles.

## 2.1.6 Définition 6

Un graphe $r = (V, E)$ est orienté si pour toute arête $y \in E$ telle que $0(y) \neq t(y)$ et pour toute autre arête $y' \in E$, l'ensemble $\{y, y'\}$ n'est pas une arête géométrique, c'est-à-dire $(0(y), t(y)) \neq (t(y'), 0(y))$.

Les arêtes d'un graphe permettent ainsi d'associer à ce dernier de multiples propriétés. Parmi celles-ci, nous retrouvons la notion de régularité d'un graphe.

Comme le lecteur pourra le constater plus tard, les graphes réguliers possèdent de multiples propriétés très intéressantes.
### 2.1.7 Définition 7

Un graphe $r = (V, E)$ est k-régulier ($k \ge 1$) si pour tout nœud $P \in V$,

$$|\{y \in E | 0(y) = P\}| = |\{y \in E | t(y) = P\}| = k \qquad (5)$$

### 2.1.8 Exemple 1

<figure><img src="image_5.png" /><figcaption>Figure 2. graphe régulier.</figcaption></figure>

## 2.2 Représentation d'un graphe

En général, un nœud d'un graphe est représenté par un point, une arête orientée est quant à elle représentée par une flèche de son origine vers sa destination. Cependant, une arête géométrique est représentée par une ligne entre ses extrémités.

Les exemples ci-dessous montrent des graphes étiquetés par des entiers ou des lettres.

<figure><img src="image_6.png" /><figcaption>Figure 3. graphe étiqueté.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 4. graphe letré.</figcaption></figure>

Un même graphe possède plusieurs représentations différentes. Cependant, quelle que soit la représentation utilisée, la structure du graphe reste inchangée. Pour pouvoir étudier uniquement la structure d'un graphe, il convient d'utiliser un outil qui permet d'ignorer l'étiquetage, c'est-à-dire de donner une équivalence structurelle. Pour cela, la notion de morphisme est utilisée.

#### 2.2.1 Définition 8

soient $r_1 = (V_1, E_1)$ et $r_2 = (V_2, E_2)$ deux graphes. Un homomorphisme de graphes est une application
$$f = (fv, f_E) : r_1 \to r_2, \qquad (6)$$

Où $fv: V_1 \to V_2$ et $f_E: E_1 \to E_2$ sont telles que, si une arête $y \in E_1$ est d'origine $P_1$ et de destination $P_2$, alors $f_E(y)$ est une arête dans $E_2$ d'origine $f_V(P_1)$ et de destination $f_V(P_2)$.

Si $f_V$ et $f_E$ sont des applications bijectives, alors $f$ est un isomorphisme.

Ainsi, deux graphes isomorphes possèdent la même structure.

## 2.3 Chemins, cycles et connexité

Les informaticiens utilisent beaucoup les graphes comme structure de données et stockent des informations dans les nœuds. Ils sont entre autre intéressés par l'implémentation d'algorithmes pour trouver le plus court chemin entre deux nœuds et procéder ainsi à une recherche plus rapide au sein du graphe.

D'abord, nous introduirons la notion de chemin et ensuite nous étudierons les cycles.

### 2.3.1 Définition 9

soit un entier $n \ge 0$. Considérons le graphe orienté suivant noté $Ch_n$:

<figure><img src="image_8.png" /><figcaption>Figure 5. graphe orienté.</figcaption></figure>

1. L'ensemble des nœuds est $V = \{0, 1, 2, ..., n\}$.

2. L'ensemble des arêtes est

$$E = \{(i, i+1) | 0 \le i \le n-1\} = \{(0,1), (1,2), ..., (n-1, n)\} \qquad (7)$$

3. La fonction d'incidence est définie de la manière suivante :

$$\varphi: E \to V * V, (i, i+1) \to (i, i+1). \qquad (9)$$

Un chemin de longueur $n$ dans un graphe $r$ est un sous-graphe $r_c$ de $r$ isomorphe à $Ch_n$. ou encore une séquence de $n$ arcs tels que chacun d'eux, sauf le dernier dispose d'une destination qui l'origine de l'arc suivant.

### 2.3.2 Exemple 2

1. L'ensemble des nœuds est $V = \mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}$

2. L'ensemble des arêtes est $E = \{(i, i+1) | i \in \mathbb{Z}_n\}$

3. La fonction d'incidence est définie de la manière suivante :

$$\varphi: E \to V * V, (i, i+1) \to (i, i+1). \qquad (10)$$

Ainsi, il existe un isomorphisme $\gamma: Ch_n \to r_c$ et un chemin peut être considéré comme une suite de nœuds $(P_0, ..., P_n)$ telle que $P_i = \gamma(i)$ pour tout $i \in \{0, ..., n\}$ et telle qu'à partir de nœud il existe une arête vers le nœud suivant dans la suite. Un chemin peut également être considéré comme une suite d'arêtes $(y_1, ..., y_n)$ telle que $y_i = \gamma((i-1), i)$ pour tout $i \in \{1, ..., n\}$ avec $t(y_i) = 0(y_i+1)$, pour tout $i \in \{1, ..., n-1\}$.

Un chemin peut être infini. Dans le cas d'un chemin fini, le premier nœud de la suite est appelé nœud de départ, le dernier nœud, nœud d'arrivée, les autres nœuds étant appelés nœuds internes.
### 2.3.3 Définition 10

Soit $n \ge 1$ un entier. Considérons le graphe orienté suivant, noté $Circ_n$ :

<figure><img src="image_9.png" /><figcaption>Figure 6. un cycle.</figcaption></figure>

## 3 Matrice d'adjacence et graphes r-partites

Tout graphe fini (c'est-à-dire possédant un nombre fini de nœuds et d'arêtes) peut être représenté par une matrice : la matrice d'adjacence.

### 3.1 Matrice d'adjacence

#### 3.1.1 Définition 11

La matrice d'adjacence de $r$, notée $A = (a_{ij})_{1 \le i, j \le n}$, est définie de la manière suivante :

$$a_{ij} = |\{y \in E | 0(y) = i, t(y) = j\}| = m+(i, j) \quad (11)$$

La matrice d'adjacence est unique à numérotation des nœuds près.

#### 3.1.2 Exemple 3

Graphe non régulier.

<figure><img src="image_10.png" /><figcaption>Figure 7. un graphe non régulier.</figcaption></figure>

$$A = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix}$$

1. L'ensemble des nœuds est $V = \mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}$

2. L'ensemble des arêtes est $E = \{(i, i+1) | i \in \mathbb{Z}_n\}$

3. La fonction d'incidence est définie de la manière suivante :

$$\varphi: E \to V * V, (i, i+1) \to (i, i+1). \quad (12)$$

Un cycle de longueur $n$ dans un graphe est un sous-graphe isomorphe à $Circ_n$. Ce sous-graphe est appelé graphe cyclique.
### 3.1.3 Définition 12

Un graphe $r = (V, E)$ est connexe s'il existe pas de partition $\{V_1, V_2\}$ de $V$ et càd $(V_1 \cup V_2=V$, et $V_1 \cap V_2=\emptyset$) $V_1 \neq \emptyset$, $V_2 \neq \emptyset$ et de sous-ensemble $E_1$, $E_2$ de $E$ tels que $E_1 \cup E_2=E$ et $E_1 \cap E_2=\emptyset$ de telle sorte que $r_1=(V_1,E_1)$ et $r_2=(V_2,E_2)$ soient deux graphes.

### 3.1.4 Remarque 1

Dans la définition précédente, l'ensemble $\{E_1, E_2\}$ ne constitue pas nécessairement une partition de $E$, car $E_1$ ou $E_2$ peut être l'ensemble vide.

La connexité d'un graphe non-orienté peut être vérifiée grâce au critère que voici.

### 3.1.5 Proposition 1

Si $r = (V, E)$ est un graphe non-orienté, $r$ est connexe si et seulement si pour tout couple de nœuds distincts $(P_1, P_2)$, il existe un chemin de $P_1$ à $P_2$.

### 3.1.6 Définition 13

Soient $r = (V, E)$ un graphe fini et $A$ sa matrice d'adjacence.

La matrice $A$ représente l'opérateur de Hecke qui envoie une fonction complexe $f$ définie sur les nœuds $V$ sur une autre fonction $A$ $f$ définie sur $V$ de la manière suivante : pour tout $P \in V$,

$$A f(p) = \sum_{\{y \in E \setminus 0(y)=P\}} f(t(y)) \quad (13)$$

L'opérateur de Hecke n'est en fait rien d'autre qu'un produit matriciel.

### 3.1.7 Proposition 2

Soient $r = (V, E)$ un graphe fini et $A= (a_{ij})_{1 \le i, j \le n}$ sa matrice d'adjacence. Alors la taille de $r$ vaut :

$$|E| = \sum_{0 \le i, j \le n} a_{ij} = \sum_{0 \le i \le n} \sum_{0 \le j \le n} a_{ij} \quad (14)$$

### 3.1.8 Exemple 4

$$A = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} \quad \|E\| = \sum_{0 \le i, j \le n} a_{ij} = 0 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + 1 + 0 + 0 + 1 + 0 + 0 = 4$$

### 3.1.9 Proposition 3

Soit $r = (V, E)$ un graphe fini. Sa matrice d'adjacence est symétrique si et seulement si $r$ est non orienté.

#### Démonstration.

Notons $A = (a_{ij})_{1 \le i, j \le n}$ la matrice d'adjacence de $r$.

$A$ est symétrique si et seulement si pour tout $i, j \in \{1, ..., n\}$, $a_{ij} = a_{ji}$ si et seulement si pour $i, j \in \{1, ..., n\}$, $|\{i, j \in E|\phi(y)=(i, j)\}|=|\{y \in E|\phi(y)=(j, i)\}|$ si et seulement si $r$ est non-orienté.

La matrice d'adjacence d'un graphe régulier possède la propriété très simple et pourtant si fondamentale que voici.

### 3.1.10 Proposition 4

Soient $r = (V, E)$ un graphe k-régulier ($k \ge 1$) sur n nœuds et $A= (a_{ij})_{1 \le i, j \le n}$ sa matrice d'adjacence.

Alors

$$\sum_{1 \le i \le n} a_{ij} = k \quad \forall 1 \le i \le n \quad (15)$$

Et
$$ \sum_{1 \le i \le n} a_{ij} = k \quad \forall 1 \le j \le n \qquad (16) $$

### Démonstration.

En effet,

$$ \sum_{1 \le j \le n} a_{ij} = \sum_{1 \le j \le n} |\{y \in E | \phi(y) = (i, j)\}| = |\{y \in E | 0(y) = i\}| = k, \quad (17) $$

La dernière égalité étant vérifiée car $r$ est k-régulier.

De la même manière, nous calculons

$$ \sum_{1 \le i \le n} a_{ij} = k \qquad (18) $$

## 3.2 Graphe r-partites

Le calcul des valeurs propres d'un graphe de taille beaucoup grande est très difficile d'une manière général sauf pour le cas des graphes finis réguliers et r-partites.

### 3.2.1 Définition 14

Un graphe $r = (V, E)$ est r-partite ($r \ge 1$) si l'ensemble des nœuds $V$ peut être divisé en $r$ ensembles non vides disjoints $V_1, \dots, V_r$ tels que :

Pour tout indice $i \in \{1, \dots, r\}$, il existe un indice $j \in \{1, \dots, r\} \setminus \{i\}$ tel que toute arête d'origine dans $V_i$ possède sa destination dans $V_j$.

### 3.2.2 Exemple 5

Ce graphe est tripartite ou 3-partite car $V_1=\{a,c\}$, $V_2=\{d,f\}$ et $V_3=\{b,e\}$ sont des sous-ensembles disjoints de $V = \{a,b,c,d\}$ tels que $\forall 1 \le i \le 3$, les éléments de $V_i$ ne sont pas liés.

<figure><img src="image_11.png" /><figcaption>Figure 8. un graphe 3-partite.</figcaption></figure>

## 4 Spectre d'un graphe

Une attention très particulière est portée à la matrice d'adjacence, car celle-ci fournit les valeurs propres du graphe.

### 4.1 Définition 15

Soient $r = (V, E)$ un graphe fini et $a \in C$.

$a$ est une valeur propre de $r$ si et seulement si $a$ est une valeur propre de sa matrice d'adjacence.

Le spectre $r$ est l'ensemble de ses valeurs propres.
## 4.2 Remarque 2

le spectre d'un graphe (fini) est indépendant de la numérotation de ses nœuds en effet, un changement de numérotation des nœuds revient à faire un changement de base. Cependant, nous savons que les valeurs propres d'une matrice ne dépendent pas de la base choisie.

## 4.3 Quelques résultats

### 4.3.1 Proposition 5

Soit $r=(V, E)$ un graphe k-régulier ($k \ge 1$) sur $n$ nœuds. Alors $k$ est une valeur propre de $r$ et pour toute valeur propre $\lambda$ de $r$, $|\lambda| \le k$.

**Démonstration.**

Grâce à la proposition 4, il est facile de voir que le vecteur $\vec{1} = (1, ..., 1)^T$ est vecteur propre de valeur propre $k$. Il reste donc à prouver que pour toute valeur propre $\lambda$ de $r$, $|\lambda| \le k$.

Considérons $v=(v_1, ..., v_n)^T$ un vecteur propre de valeur propre $\lambda$. Nous pouvons supposer, quitte à renuméroter les nœuds, que pour tout $j \ge 2$, $|v_j| \ge |v_j|$. notons $A$ la matrice d'adjacence de $r$. Comme $Av = \lambda v$, nous avons :

$$ \sum_{1 \le j \le n} a_{1j} v_{1j} = \lambda v_1 \quad (19) $$

Nous en déduisons alors,

$$ |\lambda| |v_1| \le \sum_{1 \le j \le n} a_{1j} |v_j| \le |v_1| \sum_{1 \le j \le n} a_{1j} = k \cdot |v_1|, \quad (20) $$

La dernière égalité provenant de la proposition 4.

Comme le montre la proposition suivante, la connexité d'un graphe k-régulier peut être étudiée à partir de ses valeurs propres.

### 4.3.2 Proposition 6

Soit $r = (V, E)$ un graphe non-orienté et k-régulier sur $n$ nœuds. $r$ possède $n$ valeurs propres réelles, notées $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n$.

$r$ est non-connexe si et seulement si $\lambda_1 = \lambda_2 = k$.

la section suivante accorder une attention particulière à l'étude de ces valeurs propres. C'est pourquoi par la suite, nous considérons toujours des graphes finis.

Les propositions qui offrent une méthode permettant de vérifier qu'un graphe k-régulier est bipartite. Cette méthode utilise les valeurs propres du graphe.

### 4.3.3 Proposition 7

Soit $r = (V, E)$ un graphe k-régulier ($k \ge 1$) sur $n$ nœuds. Si $r$ est bipartite, alors $k$ est une valeur propre de $r$.

**Démonstration.**

Comme $r$ est bipartite, il existe une numérotation des nœuds $V$ telle que la matrice d'adjacence de $r$ soit de la forme :

$$ A := \begin{pmatrix} 0 & A_1 \\ A_1 & 0 \end{pmatrix} $$

Où $A_1 \in \mathbb{R}^{m*(n-m)}$ et $A_2 \in \mathbb{R}^{(n-m)*m}$, pour un certain $m \in \{1, ..., n-1\}$. Grâce à la proposition 4, nous remarquons alors que le vecteur $v=(-1, ..., -1, 1, ..., 1)^T$, où $-1$ apparaît m fois et $1$ apparaît n-m fois, est un vecteur propre de valeur propre $k$.
### 4.3.4 Proposition 8

Soit $r = (V, E)$ un graphe connexe, k-régulier ($k \ge 1$) et non-orienté sur un n nœuds.
Si $k$ est une valeur propre de $r$, alors $r$ est bipartite.

**Démonstration.**

Soit $v=(v_1,...,v_n)^T$ un vecteur propre de valeur propre $-k$.

Notons $\mu := \max \{|V_i| \mid i \in \{1, \dots, \} \}$.

Pour tout $j \in \{1, \dots, \}, |V_j| = \mu$. En effet, soit $i \in \{1, \dots, \},$ tel que $|V_i| = \mu$ et notons $A=(a_{ij})_{1 \le i,j \le n}$ la matrice d'adjacence de $r$. Comme $Av = -kv$, nous en déduisons que :

$$ \sum_{1 \le j \le n} a_{ij} v_j = -k \cdot v_i \quad (20) $$

Grâce à la proposition 5, à la définition de $\mu$ et comme $|V_i| = \mu$, nous en déduisons que

$$ \sum_{j \atop a_{ij} \neq 0} a_{ij} |v_j| = \mu k. \quad (21) $$

De plus, comme $r$ est k-régulier, nous avons :

$$ \mu k = \mu \sum_{j \atop a_{ij} \neq 0} a_{ij} \quad (22) $$

nous déduisons de ces deux égalités que :

$$ \sum_{j \atop a_{ij} \neq 0} a_{ij} (\mu - |v_j|) = 0 \quad (23) $$

Comme les entrées $a_{ij}$ de la somme sont strictement positives et grâce à la définition de $\mu$, nous remarquons que pour tout $j$ tel que $a_{ij} \neq 0, \mu = |v_j|$. Si $j' \in \{1,..., n\} \setminus \{i\}$ est un nœud tel que $a_{ij'} = 0$, alors comme le graphe est non-orienté, la proposition 1 dit qu'il existe un chemin entre $i$ et $j'$. en répétant l'argument précédent de manière itérative sur tous les nœuds du chemin, nous montrons que $|v_{j'}| = \mu$.

Nous avons donc prouvé que $|v_{j'}| = \mu$, pour tout $j \in \{1,..., n\}$.

Posons alors $I := \{ i \in \{1,..., n\} | v_i = \mu \}$ et $j := \{ j \in \{1,..., n\} | v_j = -\mu \}$.

Montrons que ces deux ensembles sont non vides. Supposons par l'absurde que $j \neq \emptyset$. Dans ce cas, pour tout $i \in \{1,..., n\}, v_i = \mu > 0$. Comme $Av = -kv$, nous obtenons alors :

$$ -kv_i = \sum_{1 \le j \le n} a_{ij} v_j = \mu k, \quad (24) $$

La dernière égalité étant vérifiée car $r$ est k-régulier. Nous déduisons de cette égalité que $v_i = -\mu$, ce qui est une contradiction. Nous prouvons de la même manière que $I \neq \emptyset$.

L'ensemble $\{I, J\}$ forme donc une partition de $V$. pour montrer quefai le graphe est bipartite, prouvons les deux points suivants :

1. Pour tout $i, j \in I$, $a_{ij} = 0$. En effet, soit $i \in I$. supposons qu'il existe une entrée $a_{ij}$ de la matrice d'adjacence telle que $a_{ij} \neq 0$ et montrons que dans ce cas, le nœud $j$ appartient à l'ensemble $J$, c'est-à-dire $V_i = -\mu$. Par le même raisonnement que précédemment, nous avons l'égalité :

$$ \sum_{a_{il} \neq 0} a_{il} v_l = -k \cdot v_i = -k \cdot \mu \quad (25) $$

La dernière égalité étant vérifiée car $i \in I$. comme le graphe est k-régulier, nous déduisons de cette égalité que $v_l = -\mu$, pour tout nœud l tel que $a_{il} \neq 0$. en particulier, $v_l = -\mu$.
2. Pour tout i, j ∈ J, $a_{ij} = 0$. Ceci se prouve de la même manière que le point précédent.

### 4.3.5 Définition 16

Soit $\mathbf{r} = (V, E)$ un graphe fini et $\mathbf{k}$-régulier. Alors les valeurs propres de $\mathbf{r}$ du type $\mathbf{k} \cdot \xi$, où $\xi \in \mathbb{C}$ est de norme 1, sont appelées valeurs propres triviales du graphe.

### 4.3.6 Proposition 9

Soit $\mathbf{r} = (V, E)$ un graphe fini, connexe, orienté, $\mathbf{k}$-régulier et $\mathbf{r}$-partite (avec $\mathbf{r} \ge 1$ maximal). Alors $\xi \mathbf{k}$ est une valer propre de $\mathbf{r}$, pour tout $\xi$ de la forme : $\xi = e^{\frac{2i\pi q}{r}}$, $0 \le q < r$.

Etudions maintenant les valeurs propres triviales d'un graphe non-orienté, $\mathbf{k}$-régulier et bipartite.

### 4.3.7 Proposition 10

Soit $\mathbf{r} = (V, E)$ un graphe fini, non-oorienté, $\mathbf{k}$-régulier et bipartite. Alors les valeurs propres triviales de $\mathbf{r}$ sont $\mathbf{k}\mathbf{e}t -\mathbf{k}$.

**Démonstration.**

Comme $\mathbf{r}$ est $\mathbf{k}$-régulier, nous savons, par la proposition 5, que $\mathbf{k}$ est valeur propre. De plus, la proposition 6 nous montre que $-\mathbf{k}$ est également valeur propre. Comme $\mathbf{r}$ est non-orienté, ses valeurs propres sont réelles. Par conséquent, $\mathbf{k}$ et $-\mathbf{k}$ sont les seules valeurs propres triviales de $\mathbf{r}$.

Cette dernière proposition traite en fait le cas de tous les graphes non-orientés, $\mathbf{k}$-réguliers et $\mathbf{r}$-partites. En effet, considérons la proposition qui suit.

### 4.3.8 Proposition 11

Soit $\mathbf{r} = (V, E)$ un graphe (connexe) non-orienté et $\mathbf{r}$-partite avec $\mathbf{r} \ge 1$ maximal. Alors $\mathbf{r}=2$.

# 5 Spectre du graphe de Cayley

## 5.1 Définitions, exemples et propriétés

Les graphes de Cayley sont définis à partir d'un groupe et encodent la structure de celui-ci. Tous les groupes considérés ici seront notés additivement.

### 5.1.1 Définition 17

Soient $G$ un groupe et $S \subseteq G$ une partie de $G$.

Le graphe de Cayley $C(G, S)$ est défini de la manière suivante :

1. Le groupe $G$ est l'ensemble des nœuds.

2. Une arête est un couple de nœuds du type $(x, x + s)$ où $x \in G, s \in S$. ainsi,
   $$E = \{(x, x + s) | x \in G, s \in S\}$$

3. La fonction d'incidence $\varphi$ est l'inclusion $E \subseteq G \times G$. ainsi,
   $$\varphi: E \rightarrow G \times G, (x, x + s) \mapsto (x, x + s).$$

L'ensemble des nœuds d'un graphe de Cayley $C(G, S)$ sera trivialement noté $G$. voici un exemple de graphe de Cayley défini à partir du groupe abélien $\frac{\mathbb{Z}}{4\mathbb{Z}}$ et de l'ensemble $S = \{\mathbf{1}, \mathbf{2}\}$ :

$$1) \quad G = \mathbb{Z}_4 = \{\mathbf{0}, \mathbf{1}, \mathbf{2}, \mathbf{3}\} \text{ et } S = \{\mathbf{2}, \mathbf{3}\}$$

$$E = \{(\mathbf{0}, \mathbf{0}, +\mathbf{2}), (\mathbf{0}, \mathbf{0}, +\mathbf{3}), (\mathbf{1}, \mathbf{1}, +\mathbf{2}), (\mathbf{1}, \mathbf{1}, +\mathbf{3}), (\mathbf{2}, \mathbf{2}, +\mathbf{2}), (\mathbf{2}, \mathbf{2}, +\mathbf{3}), (\mathbf{3}, \mathbf{3}, +\mathbf{2}), (\mathbf{3}, \mathbf{3}, \mathbf{3})\}$$
$$
E = \{(\dot{0}, \dot{2}), (\dot{0}, \dot{3}), (\dot{1}, \dot{3}), (\dot{1}, \dot{0}), (\dot{2}, \dot{0}), (\dot{2}, \dot{1}), (\dot{3}, \dot{1}), (\dot{3}, \dot{2})\}
$$

<figure><img src="image_12.png" /><figcaption>**Figure 9.** Exemple d'un graphe de cayley</figcaption></figure>

$$
\begin{array}{l@{\quad}l}
2) & G = \mathbb{Z}_3 = \{\dot{0}, \dot{1}, \dot{2}, \} \text{ et } S = \{\dot{1}, \dot{2}\} \\
   & E = \{\dot{0}, \dot{1}\}, (\dot{0}, \dot{2}), (\dot{1}, \dot{2}), (\dot{1}, \dot{0}), (\dot{2}, \dot{0}), (\dot{2}, \dot{1})\}
\end{array}
$$

<figure><img src="image_13.png" /><figcaption>**Figure 10.** Exemple d'un graphe de cayley</figcaption></figure>

**5.1.2 Proposition 12**

Soient $G$ un groupe et $S \subseteq G$ une partie de $G$. Le graphe de Cayley $C(G, S)$ est $|S|$-régulier.

Démonstration.

Soit $g \in G$ un nœud du graphe.

$$
|\{y \in E | 0(y) = g\}| = |\{(g, g + s) | s \in S\}| = |S| \qquad (26)
$$

De plus,

$$
|\{y \in E | t(y) = g\}| = |\{(g - s, g) | s \in S\}| = |S| \qquad (27)
$$

La |S|-régularité du graphe de Cayley est ainsi vérifiée.

**5.1.3 Proposition 13**

soient $G$ un groupe et $S \subseteq G$ une partie de $G$. nous considérons le graphe de Cayley $C(G, S)$. Alors pour tout couple de nœuds $P_1, P_2 \in G$, il existe au plus une arête $y \in E$ telle que

$$
\varphi(y) = (P_1, P_2). \tag{28}
$$

Démonstration.

Soient $P_1, P_2 \in G$ deux nœuds quelconques.

* Cas 1 : $P_1 = P_2 = P$. si $y \in E$ est une boucle en $P$, alors il existe un élément $s \in S$ tel que $P + s = P$. ceci n'est possible que si $s=0$.
➤ Cas 2 : $P_1 \neq P_2$. Supposons avoir deux arêtes $y_1, y_2 \in E$ telles que :

$$0(y_1)=0(y_2)=P_1 \text{ et } t(y_1)=t(y_2)=P_2 \qquad (29)$$

La définition d'un graphe de Cayley fournit deux éléments $k_1, k_2 \in S$ tels que :

$$P_2 = P_1 + k_1 \text{ et } P_2 = P_1 + k_2 \qquad (30)$$

Ceci n'est possible que si $k_1=k_2$. Par conséquent, $y_1 = y_2$.

### 5.1.4 Corollaire 1

Tout graphe de Carley non-orienté est simplement non-orienté. L'orientation d'un graphe de Cayley $C(G, S)$ et la structure de la partie $S$ sont intimement liées. Le résultat suivant le montre.

### 5.1.5 Définition 18

Soient $G$ un groupe et $S \subseteq G$ une partie de $G$. Le sous-ensemble $S$ est symétrique si pour tout élément $s \in S$, son opposé se trouve également dans $S$.

### 5.1.6 Proposition 14

Soit $r = C(G, S)$ un graphe de Cayley. $r$ est simplement non-orienté si et seulement si $S$ est symétrique.

**Démonstration.**

($\Leftarrow$) soit $y := (x, x + s) \in E$ une arête du graphe. Il faut prouver qu'il existe une et une seule arête $\bar{y} \in E$ telle que

$$(0(y), t(y)) = (t(\bar{y}), 0(\bar{y})). \qquad (31)$$

Comme $S$ est symétrique, le couple $(x+s, x)$ est bien une arête du graphe et elle satisfait la condition. Par la proposition 13, nous savons qu'une telle arête est unique.

($\Rightarrow$) soit $s \in S$. si $s = 0$, il n'y a rien à prouver. Nous supposons donc $s \neq 0$. Il faut montrer que $-s \in S$. pour cela considérons l'arête $y := (x, x+s) \in E$, avec $x \in G$ quelconque. Comme le graphe $C(G, S)$ est simplement non-orienté, il existe une unique flèche $\bar{y} := (z, z+s')$, $z \in G, s' \in S$ telle que

$$\begin{cases} z = x + s \\ x = z + s' \end{cases}$$

Nous en déduisons que $s' = -s \in S$

### 5.1.7 Proposition 15

Soient le groupe $G = \mathbb{Z}_n$ ($n \geq 1$) et $S = \{k+n1\}$ et $S = \{k+n\mathbb{Z}\}$ une partie de $G$, avec $k$ premier à n. alors le graphe de Cayley $C(G, S)$ est cyclique.

<figure><img src="image_14.png" /><figcaption>**Figure 9.** un graphe de cayley cyclique.</figcaption></figure>
6 Conclusion

* Un graphe est une structure de données qui permet de modéliser des réseaux, des systèmes de communication et autres domaines d'applications spécifiques;

* Dans ce travail, cette théorie s'est focalisée sur l'étude du spectre des graphes de Cayley par l'existence d'un lien entre les valeurs propres et la connexité de ce type des graphes, d'une part et d'autre part en s'appuyant sur les groupes abéliens et la théorie des représentations de ces groupes;

* Perspectives, nous envisageons regarder les graphes de **Ramanujan** qui du reste sont des graphes k-reguliers et caractérisés par certaines propriétés sur leurs valeurs propres, l'objectif étant de construire une famille finie de tels graphes en s'appuyant sur la théorie de Galois.

REFERENCES

[1] Ahuja, T.L. Magnanti Et J.B. Orlin. Networks Flows, Prentice Hall, 1993.

[2] N. Bourbaki, Séminaire, PP.253-260, 1996-1997.

[3] J.H. Conway et N.J.A. Sloane, Sphere packings, lattices and groups, springer-verlag, PP.452, 1988.

[4] R. Faure, B. Lamaire et C. Picouleau, Precis de recherche opérationnelle, Dunod, 2014.

[5] Friedman, R. Murty, J-P. Tillich, Spectral estimates for Abelian graphs, PP.111-121, 2004.

[6] W. Fulton, J. Harris, Representation theory a first course, springer, 1991.

[7] S. Hoory, N. Linial et A. Wigderson, Expander graphs and their applications, PP.452-457, 469-481, 503-514, 522-536, 2006.

[8] L. Manya Ndjadi, Cours de Recherche operationnelle, inedit, Université de Kinshasa, 1996.