Adjacency algebra

In algebraic graph theory, the adjacency algebra of a graph G is the algebra of polynomials in the adjacency matrix A(G) of the graph. It is an example of a matrix algebra and is the set of the linear combinations of powers of A.[1]

Some other similar mathematical objects are also called "adjacency algebra".

Properties

Properties of the adjacency algebra of G are associated with various spectral, adjacency and connectivity properties of G.

Statement. The number of walks of length d between vertices i and j is equal to the (i, j)-th element of Ad.[1]

Statement. The dimension of the adjacency algebra of a connected graph of diameter d is at least d + 1.[1]

Corollary. A connected graph of diameter d has at least d + 1 distinct eigenvalues.[1]

References

  1. 1 2 3 4 Algebraic graph theory, by Norman L. Biggs, 1993, ISBN 0521458978, p. 9


This article is issued from Wikipedia - version of the 10/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.