The main eigenvalues and number of walks in self-complementary graphs

Abstract

The number of walks of an arbitrary length in a graph depends only on its main eigenvalues and the orthogonal projections onto the associated eigenspaces. Given that a graph is known to be self-complementary, it is shown that its main eigenvalues are easily recognizable from the spectrum alone. Various results on self-complementary graphs (sc-graphs) are derived. An upper bound for the number (less than ) of main eigenvalues of -vertex sc-graphs is established. An explicit formula for the number of walks of length less than in sc-graphs is also presented. We conclude by showing that, for a self-complementary graph, some or all of the coefficients of the main characteristic polynomial suffice to yield the number of walks of any length.