In algebraic graph theory, 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 discret ...

''G'' is the

algebra Algebra is a branch of mathematics that deals with abstract systems, known as algebraic structures, and the manipulation of expressions within those systems. It is a generalization of arithmetic that introduces variables and algebraic ope ...

polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...

s in the

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...

''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'') (alterna ...

and is the set of the

linear combination In mathematics, a linear combination or superposition is an Expression (mathematics), expression constructed from a Set (mathematics), set of terms by multiplying each term by a constant and adding the results (e.g. a linear combination of ''x'' a ...

s of

power Power may refer to: Common meanings * Power (physics), meaning "rate of doing work" ** Engine power, the power put out by an engine ** Electric power, a type of energy * Power (social and political), the ability to influence people or events Math ...

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, 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 as an "inverted pendulum" gait in which the body vaults over ...

s of length ''d'' between vertices ''i'' and ''j'' is equal to the (''i'', ''j'')-th element of ''A^d''. ''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 coo ...

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 ...

diameter In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...

''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 is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a ...

Spectral Properties

Adjacency algebra is closely linked with

Spectral graph theory In mathematics, spectral graph theory is the study of the properties of a Graph (discrete mathematics), graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacen ...

due to both them having the involvement of the

Adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...

of a graph and its eigenvalues. Spectral graph theory is about how eigenvalues, eigenvectors, and other linear-algebraic quantities give us useful information about a graph, for example about how well-connected it is, how well we can cluster or color the nodes, and how quickly random walks converge to a limiting distribution. In the context of

the eigenvectors and the eigenvalues of graph's

provide valid and essential insights into several structural properties such as connectivity, clustering, coloring, and the behavior of random walks, these insights are tightly tied to the adjacency algebra generated by the

, including all its powers and linear combinations. Both concepts are concerned with the adjacency matrix but approach it differently and are looked with different perspectives,

focuses more on the specific spectral properties (eigenvalues and eigenvectors) to extract information about the graph's connectivity. In contrast adjacency algebra works more with matrix powers and linear combinations to understand the graphs structure more algebraically.

Applications of Adjacency Algebra

Adjacency algebra has several applications both in mathematics and computer science. Adjacency algebra can be utilized in network analysis and graph theory, where the powers of the adjacency matrix can help to determine how connected a specific graph is by tracking paths of length ''k'' between vertices. It can also be used with graph partitioning and graph theory based AI and

Large language model A large language model (LLM) is a language model trained with self-supervised machine learning on a vast amount of text, designed for natural language processing tasks, especially language generation. The largest and most capable LLMs are g ...

References

Algebraic graph theory {{graph-stub