Characteristic polynomial of a graph

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

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

Литература

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