# Characteristic polynomial of a graph

Перейти к:навигация, поиск

Characteristic polynomial of a graphхарактеристический полином графа.

Given a graph $\,G$, the polynomial $\,p_{G}(\lambda) = \det(\lambda I - A_{G})$, where $\,A_{G}$ is the adjacency matrix of $\,G$. This clearly does not depend on the labeling of vertices. The roots of the characteristic polynomial, i.e. the eigenvalues of $\,A_{G}$, are called the eigenvalues of the graph $\,G$. The spectrum of $\,G$ is the set of solutions to $\,p(\lambda) = 0$ denoted by $S_{p} = \{\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n}\}$ with $\lambda_{1} \geq \lambda_{2} \geq \ldots, \lambda_{n}$. The first eigenvalue $\,\lambda_{1}$ is called the index or spectral radius.

## Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.