Monash University
4684144_monash_120804.pdf (774.36 kB)

Counting subgraphs of regular graphs using spectral moments

Download (774.36 kB)
posted on 2017-02-23, 02:39 authored by Minchenko, Marsha Elizabeth
This thesis introduces a novel approach to counting subgraphs of regular graphs. This is useful for relating the algebraic properties of a graph G to its structural properties; namely the eigenvalues of the adjacency matrix of G to the counts of various subgraphs of G. It was previously known that the lth spectral moment of G is equal to the number of closed walks of length in G. The first four spectral moments were found to relate the eigenvalues of G to the number of vertices, edges, triangles, and quadrilaterals in G. For bipartite regular graphs, the 6th spectral moment was found to relate the eigenvalues of G to the degree and the number of vertices, quadrilaterals, and hexagons in G. We present a general method for counting all closed walks of a given length in connected regular graphs. We describe a set of base walks and their possible extensions to the set of all closed walks of G. All the extensions are handled using generating functions, resulting in a substantial reduction in the amount of direct enumeration required. Consequently, we are able to derive equations relating the lth spectral moment to the degree, the number of vertices, and the counts of various subgraphs in a regular graph. Such equations have been used to help in the search for members of interesting families of graphs. One such graph family is the integral graphs. These have only integers as eigenvalues. We build on previous results that give a list of spectra (the eigenvalues with their multiplicities) that are possible for a graph that is connected, 4-regular, bipartite, and integral. From this list, we consider the subgraph configurations necessary to eliminate spectra that cannot be realized by a vertex-transitive graph. Using this refined list, we are able to find all connected, 4-regular, integral Cayley graphs. We present a method for counting connected subgraphs H of a strongly regular graph. Strongly regular graphs are r-regular with e common neighbours between adjacent vertices, and f common neighbours between non-adjacent vertices. For some subgraphs H, we are able to express the number of copies of H in terms of r, e, f, and the number of vertices. Counts of other subgraphs are calculated in terms of the counts of smaller subgraphs. We use basic counting arguments to prove these results and outline the algorithm which applies these results recursively on subgraphs. We give examples of the equations obtained for several cases of parameter values where it is yet to be established whether strongly regular graphs exist. We look at how both sets of equations derived in this thesis can be used to investigate the ‘missing’ Moore graph. Moore Graphs are strongly regular graphs with e = 0 and f = 1. Some well known examples are the Petersen graph and the Hoffman-Singleton graph. It is not known if a 57- regular Moore graph exists. If it does exist then it is integral with spectrum {57, 7^1729, -8^1520}. Our equations give further insights into the structure of the ‘missing’ Moore graph such as the numbers of various cycles and theta graphs. It is our hope that our equations for counting subgraphs in regular graphs and for counting subgraphs in strongly regular graphs will be useful in various ways. These include finding other specified families of graphs, finding the numbers of subgraphs of interest, investigating co-spectral pairs of graphs, and proving the non-existence of graphs.


Campus location


Principal supervisor

Ian M. Wanless

Year of Award


Department, School or Centre



Doctor of Philosophy

Degree Type



Faculty of Science