TOPICS
Search

Adjacency Matrix


The adjacency matrix, sometimes also called the connection matrix, of a simple labeled graph is a matrix with rows and columns labeled by graph vertices, with a 1 or 0 in position (v_i,v_j) according to whether v_i and v_j are adjacent or not. For a simple graph with no self-loops, the adjacency matrix must have 0s on the diagonal. For an undirected graph, the adjacency matrix is symmetric.

AdjacencyMatrix

The illustration above shows adjacency matrices for particular labelings of the claw graph, cycle graph C_4, and complete graph K_4.

AdjacencyMatrices

Since the labels of a graph may be permuted without changing the underlying graph being represented, there are in general multiple possible adjacency matrices corresponding to a given simple graph. In particular, the number N_A(G) of distinct adjacency matrices for a simple unlabeled graph G with vertex count n=|G| and automorphism group order |Aut(G)| is given by

 N_A=(|G|!)/(|Aut(G)|),

where |G|! is the number or permutations of vertex labels. The illustration above shows the 4!/8=3 possible adjacency matrices of the cycle graph C_4.

The adjacency matrix of a labeled n-digraph D is the binary square matrix of order n whose (i,j)th entry is 1 iff (i,j) is an edge of D.

The adjacency matrix of a graph can be computed in the Wolfram Language using AdjacencyMatrix[g], with the result being returned as a sparse array.

A different version of the adjacency is sometimes defined in which diagonal elements are a_(ii)=0 and a_(ij)=1 if v_i and v_j are adjacent and -1 otherwise (e.g., Goethals and Seidel 1970).

A weighted adjacency matrix A_f of a simple graph can also be defined for a real positive symmetric function f(d_i,d_j) on the vertex degrees d_i of a graph (Das et al. 2018, Zheng et al. 2022).


See also

Adjacency List, Graph Bandwidth, Incidence Matrix, Integer Matrix, Weighted Adjacency Matrix

Portions of this entry contributed by Lorenzo Sauras-Altuzarra

Explore with Wolfram|Alpha

References

Chartrand, G. Introductory Graph Theory. New York: Dover, p. 218, 1985.Das, K.; Gutman, I.; Milovanović, I.; Milovanović, E.; and Furtula, B. "Degree-Based Energies of Graphs." Linear Algebra Appl. 554, 185-204, 2018.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 69-73, 2000.Goethals, J.-M. and Seidel, J. J. "Strongly Regular Graphs Derived from Combinatorial Designs." Can. J. Math. 22, 597-514, 1970.Skiena, S. "Adjacency Matrices." §3.1.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 81-85, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 6-9, 2000.Zheng, R.; Su, P.; and Jin. S. "Arithmetic-Geometric Matrix of Graphs and Its Applications." Appl. Math. Comput. 42, 127764, 1-11, 2023.

Referenced on Wolfram|Alpha

Adjacency Matrix

Cite this as:

Sauras-Altuzarra, Lorenzo and Weisstein, Eric W. "Adjacency Matrix." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/AdjacencyMatrix.html

Subject classifications