In
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. There are three main branches of algebraic graph th ...
, the adjacency algebra of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
''G'' is the
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary ...
of
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
s in the
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
''A''(''G'') of the graph. It is an example of a
matrix algebra
In abstract algebra, a matrix ring is a set of matrices with entries in a ring ''R'' that form a ring under matrix addition and matrix multiplication . The set of all matrices with entries in ''R'' is a matrix ring denoted M''n''(''R'')Lang, ''U ...
and is the set of the
linear combinations of
power
Power most often refers to:
* Power (physics), meaning "rate of doing work"
** Engine power, the power put out by an engine
** Electric power
* Power (social and political), the ability to influence people or events
** Abusive power
Power may a ...
s of ''A''.
[Algebraic graph theory, by Norman L. Biggs, 1993, ]
p. 9
/ref>
Some other similar mathematical objects are also called "adjacency algebra".
Properties
Properties of the adjacency algebra of ''G'' are associated with various spectral
''Spectral'' is a 2016 3D military science fiction, supernatural horror fantasy and action-adventure thriller war film directed by Nic Mathieu. Written by himself, Ian Fried, and George Nolfi from a story by Fried and Mathieu. The film stars ...
, adjacency and connectivity properties of ''G''.
''Statement''. The number of walk
Walking (also known as ambulation) is one of the main gaits of terrestrial locomotion among legged animals. Walking is typically slower than running and other gaits. Walking is defined by an ' inverted pendulum' gait in which the body vaults ...
s of length ''d'' between vertices ''i'' and ''j'' is equal to the (''i'', ''j'')-th element of ''Ad''.[
''Statement''. The ]dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coor ...
of the adjacency algebra of a connected graph
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...
of diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...
''d'' is at least ''d'' + 1.[
''Corollary''. A connected graph of diameter ''d'' has at least ''d'' + 1 distinct ]eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted ...
s.[
]
References
Algebraic graph theory
{{combin-stub