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

Abstract : 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.
Document type :
Theses
Complete list of metadatas

Cited literature [99 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00956183
Contributor : Claire Lucas <>
Submitted on : Wednesday, March 5, 2014 - 11:54:25 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 PM
Long-term archiving on : Thursday, June 5, 2014 - 12:05:26 PM

Identifiers

  • HAL Id : pastel-00956183, version 1

Collections

Citation

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. ⟨pastel-00956183⟩

Share

Metrics

Record views

548

Files downloads

1168