In our last encounter, we saw how there is a matrix naturally associated with every graph, and it can be used for representing the graph on a computer. While this already merits giving adjacency matrices our attention as useful constructs, we shall now see that there is a whole lot more to them than just a data structure.
I'd like to introduce some motivation for the study of this and related structures.
Given two graphs , we say that a bijective function is a graph isomorphism if . We say that and are isomorphic, and we note this . The idea is that two isomorphic graphs are really the same graph, just under a relabeling of the nodes. Most of the properties we are interested in when studying graphs are preserved under graph isomorphism. For instance, knowing that :
- is connected is connected.
- Every cycle in has a unique cycle image in , and obviously .
- , the chromatic number. In general, and have the same chromatic polynomial. We will discuss this polynomial in further posts.
- and have the same degree sequence.
- , with the clique number (size of the largest clique, a maximal complete subgraph).
- and have the same vertex cover and edge cover numbers.
As you can see, many interesting properties of graphs are preserved by graph isomorphisms. Properties that do not talk solely about the structure of the graph, but perhaps the representation, need not be preserved under isomorphism. A common example of this is: if we've represented our nodes as numbers from to , graph isomorphism does not preserve the quantity .
Now, here is how this relates to adjacency matrices.
Lemma. Given two graphs , with adjacency matrices and respectively, and calling , then there exists a permutation matrix such that
where denotes the transpose of .
Thus, the problem of finding whether or not two graphs are isomorphic is equivalent to finding if their adjacency matrices are simply permutations of eachother. This makes sense, since the intuitive idea of a graph isomorphism is that it doesn't care if nodes have been relabeled or reordered.
An interesting offshoot of this is that the problem of finding whether or not two graphs are isomorphic (called
GRAPH-ISOMORPHISM in complexity theory) has an unknown complexity. It is known to be in NP, but it is not known if it is in NP-complete, or if it's in P, or where. It has its own complexity class, called GI. This algebraic approach lets us attack the problem using the tools of linear algebra. It is generalized by the mathematical branch of algebraic graph theory.
Another interesting property of adjacency matrices, is that they allow us to compute the amount of walks from a node to another, purely algebraically. A walk of length from to in a graph is an ordered list of nodes, where each node shares an edge with the next one in the list, the first node is , and the last node is . This assertion is formalized as such:
Lemma. Let be a graph, its adjacency matrix. Let , and let be the amount of walks of length from node to node . Then .
Knowing this, we can derive some other information about a graph. For instance, the number of induced subgraphs that has, call it is exactly
We also have that
The proofs of these facts are left as an exercise, they are not hard.
An interesting class of graphs is those such that , for some constant . These are called the -regular graphs. We shall now prove the following result about the adjacency matrix of a -regular graph:
Lemma. Let be a -regular graph, with its adjacency matrix. Then , where is the matrix's spectral radius, .
An easy property related to regulaity, is that there are no -regular graphs with , such that and are both odd. The proof is a straightforward application of the handshake lemma. If we wanted to do this again with the adjacency matrix, the proof revolves around the fact that adjacency matrices always have an even amount of s by virtue of being symmetric, and if we have an odd amount of columns, and each column has an odd amount of s, then the amount of s in the matrix would be odd, which we know can't happen.
When a property of a graph is preserved under graph isomorphism, we call it a graph property, or a graph invariant. Given that two isomorphic graphs share the same adjacency matrix, only under a permutation of the rows and columns, this tells us that some properties of the adjacency matrix are graph invariants. For instance
- Since for any invertible matrix , where is the characteristic polynomial of A, and since for a permutation matrix , , we have that the characteristic polynomial is a graph invariant.
- The same as above holds for the minimal polynomial, of an adjacency matrix.
- The set of eigenvalues of a matrix, along with their multiplicity, is called the spectrum of a matrix. Since isomorphic graphs have similar matrices (in particular, this kind of similarity is called permutation-similarity), they share eigenvalues.
One usually talks about the spectrum of the graph, and the characteristic or minimal polynomial of the graph, referring to its adjacency matrix. Note, however, that while being isomorphic implies these qualities, the converse does not hold. For example, the following two graphs (taken from Godsil & Royle's Algebraic Graph Theory) have the same characteristic polynomial, and thus share a spectrum:
They both have adjacency matrices with the characteristic polynomial , yet they are clearly not isomorphic. The problem here is that their adjacency matrices are similar, but not permutation similar. In particular, we see how planarity is not encoded in the graph's spectrum, nor is the degree of its vertices.
I hope you got a taste of how we can extract information about a graph using its adjacency matrix, and why it is important other than because of its use as a data structure. The fields of algebraic graph theory and, in particular, spectral graph theory, are the ones who study this structure and a related one, the incidence matrix, which we will see in future discussions.