Trois essais sur les relations entre les invariants structuraux des graphes et le spectre du Laplacien sans signe - PASTEL - Thèses en ligne de ParisTech Accéder directement au contenu
Thèse Année : 2013

On relations between structural invariants of graphs and the signless Laplacian spectrum

Trois essais sur les relations entre les invariants structuraux des graphes et le spectre du Laplacien sans signe

Résumé

In the last five years, much attention was devoted to the signless Laplacian of a graph by the scientific community. One of the main reasons for this interest is the intuition, shared by many researchers on the basis of studies concerning small graphs, that more graphs are determined by their signless Laplacian spectrum than by those of the adjacency and Laplacian matrices. Results presented in this thesis brought new elements on the informations hidden in the spectrum of this matrix. On the one hand, we present relations between structural graph invariants and an eigenvalue of the signless Laplacian. On the other hand, we present families of extremal graphs for two of its eigenvalues, with and without additional constraints on the shape of the graph. The families obtained for these problems are very similar to the ones defined in the same conditions for the adjacency matrix eigenvalues. This lead to the definition of families of graphs for which the signless Laplacian spectrum or one of its eigenvalues together with the number of vertices and a structural invariant are sufficient to determine the graph. These results are very similar to those concerning the adjacency matrix spectrum and then support the idea that the signless Laplacian spectrum might determine graph at least as well as the adjacency matrix spectrum.
Le spectre du Laplacien sans signe a fait l'objet de beaucoup d'attention dans la communauté scientifique ces dernières années. La principale raison est l'intuition, basée sur une étude des petits graphes et sur des propriétés valides pour des graphes de toutes tailles, que plus de graphes sont déterminés par le spectre de cette matrice que par celui de la matrice d'adjacence et du Laplacien. Les travaux présentés dans cette thèse ont apporté des éléments nouveaux sur les informations contenues dans le spectre cette matrice. D'une part, on y présente des relations entre les invariants de structure et une valeur propre du Laplacien sans signe. D'autre part, on présente des familles de graphes extrêmes pour deux de ses valeurs propres, avec et sans contraintes additionnelles sur la forme de graphe. Il se trouve que ceux-ci sont très similaires à ceux obtenus dans les mêmes conditions avec les valeurs propres de la matrice d'adjacence. Cela aboutit à la définition de familles de graphes pour lesquelles, le spectre du Laplacien sans signe ou une de ses valeurs propres, le nombre de sommets et un invariant de structure suffisent à déterminer le graphe. Ces résultats, par leur similitude avec ceux de la littérature viennent confirmer l'idée que le Laplacien sans signe détermine probablement aussi bien les graphes que la matrice d'adjacence.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
_manuscritThese.pdf (1.37 Mo) Télécharger le fichier
Loading...

Dates et versions

pastel-00956183 , version 1 (05-03-2014)

Identifiants

  • HAL Id : pastel-00956183 , version 1

Citer

Claire Lucas. Trois essais sur les relations entre les invariants structuraux des graphes et le spectre du Laplacien sans signe. Autre [cs.OH]. Ecole Polytechnique X, 2013. Français. ⟨NNT : ⟩. ⟨pastel-00956183⟩
351 Consultations
1333 Téléchargements

Partager

Gmail Facebook X LinkedIn More