Adjacency algebra
Encyclopedia
In algebraic graph theory
, the adjacency algebra of a graph
G is the algebra
of polynomial
s in the adjacency matrix
A(G) of the graph. It is an example of a matrix algebra and is the set of the linear combination
s of powers of A.
Some other similar mathematical objects are also called "adjacency algebra".
, 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.
Statement. The dimension of the adjacency algebra of a connected graph of diameter d is at least d + 1.
Corollary. A connected graph of diameter d has at least d distinct eigenvalues.
Algebraic graph theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches...
, the adjacency algebra of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
G is the algebra
Algebra (ring theory)
In mathematics, specifically in ring theory, an algebra over a commutative ring is a generalization of the concept of an algebra over a field, where the base field K is replaced by a commutative ring R....
of polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s in the adjacency matrix
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
A(G) of the graph. It is an example of a matrix algebra and is the set of the linear combination
Linear combination
In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results...
s of powers of A.
Some other similar mathematical objects are also called "adjacency algebra".
Properties
Properties of the adjacency algebra of G are associated with various spectralSpectral graph theory
In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix....
, 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.
Statement. The dimension of the adjacency algebra of a connected graph of diameter d is at least d + 1.
Corollary. A connected graph of diameter d has at least d distinct eigenvalues.