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  according to whether  and  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.

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

Since the labels of a graph may be permuted without changing the underlying graph being represented, there are in general multiple possible adjacency matrices for a given graph. In particular, the number  of distinct adjacency matrices for a graph  with vertex count  and automorphism group order  is given by

where  is the number or permutations of vertex labels. The illustration above shows the  possible adjacency matrices of the cycle graph .

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  and  if  and  are adjacent and  otherwise (e.g., Goethals and Seidel 1970).

REFERENCES

Chartrand, G. Introductory Graph Theory. New York: Dover, p. 218, 1985.

Devillers, J. and A. T. Balaban (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.