# Spectral graph theory Spectral graph theory (Redirected from Perlis theorem) Ir para a navegação Ir para a pesquisa Em matemática, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix.

The adjacency matrix of a simple undirected graph is a real symmetric matrix and is therefore orthogonally diagonalizable; its eigenvalues are real algebraic integers.

While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant, although not a complete one.

Spectral graph theory is also concerned with graph parameters that are defined via multiplicities of eigenvalues of matrices associated to the graph, such as the Colin de Verdière number.

Conteúdo 1 Cospectral graphs 1.1 Graphs determined by their spectrum 1.2 Cospectral mates 1.3 Finding cospectral graphs 2 Cheeger inequality 2.1 Cheeger constant 2.2 Cheeger inequality 3 Hoffman–Delsarte inequality 4 Historical outline 5 Veja também 6 Referências 7 External links Cospectral graphs Two graphs are called cospectral or isospectral if the adjacency matrices of the graphs are isospectral, isso é, if the adjacency matrices have equal multisets of eigenvalues.

Two cospectral enneahedra, the smallest possible cospectral polyhedral graphs Cospectral graphs need not be isomorphic, but isomorphic graphs are always cospectral.

Graphs determined by their spectrum A graph {estilo de exibição G} is said to be determined by its spectrum if any other graph with the same spectrum as {estilo de exibição G} é isomórfico a {estilo de exibição G} .

Some first examples of families of graphs that are determined by their spectrum include: The complete graphs. The finite starlike trees. Cospectral mates A pair of graphs are said to be cospectral mates if they have the same spectrum, but are non-isomorphic.

The smallest pair of cospectral mates is {K1,4, C4 ∪ K1}, comprising the 5-vertex star and the graph union of the 4-vertex cycle and the single-vertex graph, as reported by Collatz and Sinogowitz dentro 1957.

The smallest pair of polyhedral cospectral mates are enneahedra with eight vertices each. Finding cospectral graphs Almost all trees are cospectral, ou seja, as the number of vertices grows, the fraction of trees for which there exists a cospectral tree goes to 1. A pair of regular graphs are cospectral if and only if their complements are cospectral. A pair of distance-regular graphs are cospectral if and only if they have the same intersection array.

Cospectral graphs can also be constructed by means of the Sunada method. Another important source of cospectral graphs are the point-collinearity graphs and the line-intersection graphs of point-line geometries. These graphs are always cospectral but are often non-isomorphic. Cheeger inequality The famous Cheeger's inequality from Riemannian geometry has a discrete analogue involving the Laplacian matrix; this is perhaps the most important theorem in spectral graph theory and one of the most useful facts in algorithmic applications. It approximates the sparsest cut of a graph through the second eigenvalue of its Laplacian.

Cheeger constant Main article: Cheeger constant (teoria dos grafos) The Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: por exemplo, constructing well-connected networks of computers, card shuffling, and low-dimensional topology (em particular, the study of hyperbolic 3-manifolds).