Walks and CDCs


As an undergraduate, I worked on a reserach project on walks and CDCs of graphs, primarily in collaboration with my undergraduate supervisor Prof. Irene Sciriha.

This webpage provides the basic definitions necessary for understanding the objects I worked on, together with various research resources, most notably a Wolfram Mathematica™ package for graph computations.

Basic Definitions

The walk matrix of a graph is the matrix with columns \[\mathbf W = \begin{pmatrix}| & | & | & & | \\ \boldsymbol 1 & \mathbf A\boldsymbol 1 & \mathbf A^2\boldsymbol 1 & \cdots & \mathbf A^{p-1}\boldsymbol 1 \\ | & | & | & & | \end{pmatrix},\] where \(\mathbf A\) is the adjacency matrix of the graph, \(\boldsymbol 1\) is the all-ones vector \((1,\dots,1)\) and \(p\) is the largest positive integer for which the columns of \(\mathbf W\) remain linearly independent. It is not difficult to see that the \(ij\)th entry in the matrix is the number of distinct walks of length \(j\) in the graph starting from vertex \(i\).

The canonical double cover of a graph \(G\) is the graph obtained by making two copies of the vertex set of \(G\), and connecting the vertices in one copy to the neighbours it originally had in the other; here are two examples.

CDC Examples

The question we studied was mainly the following: what can we say about two graphs \(G\) and \(H\) if \(\operatorname{CDC}(G)\simeq\operatorname{CDC}(H)\)? For instance, if \(G\) is connected, it's not necessarily the case that \(H\) is connected: \[\operatorname{CDC}(2\,K_3) \simeq 2\,C_6 \simeq \operatorname{CDC}(C_6).\] On the other hand, if \(G\) has an isolated vertex, \(H\) must have one. This gave rise to a nice proof technique: in order to prove a statement \(\varphi\), we assume that \(G\) has no isolated vertices, and that \(\operatorname{CDC}(G)=\operatorname{CDC}(H)\). Then we show \(\lnot\varphi\) implies that \(H\) has an isolated vertex, which is a contradiction.

Using this technique, we were able to show that “\(G\) and \(H\) have the same CDC” is equivalent to a weaker version of isomorphism (which Lauri et. al. called a two-fold isomorphism): that there are two permutation matrices \(\mathbf P\) and \(\mathbf Q\) such that the adjacency matrices satisfy \(\mathbf P\mathbf A_G\mathbf Q = \mathbf A_H\). (Ordinary graph isomorphisms correspond to a single permutation matrix \(\mathbf P\) such that \(\mathbf P\mathbf A_G\mathbf P^{-1} = \mathbf A_H\).) But this does not add much freedom to generate such graph pairs, since given two random permutation matrices, it is highly unlikely that \(\mathbf P\mathbf A_G\mathbf Q\) is also the adjacency matrix of some other graph.

It turns out (and we showed that) having the same CDC implies that the walk matrices are the same; which means that the graphs have same number of walks of any length, once an appropriate correspondence of the vertices is established. Despite being a strong structural condition on the pairs, it is not a sufficient condition for a given pair of graphs to have the same CDC.

Graphs which appeared in my research

In my undergraduate dissertation, I went on to establish a hierarchy of relationships which pairs of graphs can have, involving CDC's, and the standard spectral objects which appear in the theory of walks in graphs (walk matrices, main eigenvalues, main eigenspaces, etc.). While conducting research to establish some of these, a lot of visually appealing examples of graph pairs cropped up, some of them are shown above. This hierarchy was published in the journal Discussiones Mathematicæ Graph Theory, and in the same paper there is also a list of all 32 non-isomorphic graph pairs with isomorphic CDCs. This list is available in PDF form in the appendix of my undergraduate dissertation, or in the section below.

Graphs with the same CDC

While I was working on my undergraduate dissertation, I obtained an exhaustive list of all pairs of non-isomorphic graphs on ⩽ 8 vertices which have the same CDC (i.e., all the pairs of graphs which are TF-isomorphic). I had also computed all such pairs on 9 vertices. You can download the corresponding graph numbers in CSV format below.

The numbers correspond to the graphs in Brendan McKay's graph data. You can easily import these graphs into Mathematica, e.g.,

Click on code to copy to clipboard
CDC Graph Data Example

Notice I've made use of some commands from the Walks package which you can obtain below.

Graphs with the same CDC on 8 Vertices

I've made the detailed list of pairs on 8 vertices available on this webpage. In addition to the pairs, you can find their walk matrices, eigenvalues, CDCs and animated Ryser switches.

Mathematica Package

Mathematica Logo

Wolfram Mathematica™ is an incredibly powerful piece of software which can perform almost any kind of computation imaginable, and unsurprisingly it is very handy for performing computations on graphs. (Unfortunately Mathematica is not free, neither in the libre sense, nor in the gratis sense, but if you are a student you can probably get it for free.)

The Walks Mathematica package, in addition to various walk/CDC related commands, provides plenty of nice commands which are useful for working with matrices of graphs in general. It is very easy to download and install.

Latest version: v1.2 (August 2022)