Clique complexes of strongly regular graphs, their eigenvalues, and cohomology groups
Preprint
Abstract
It is known that non-isomorphic strongly regular graphs with the same parameters must be cospectral (have the same eigenvalues). In this paper, we investigate whether the spectra of higher order Laplacians associated with these graphs can distinguish them. In this direction, we study the clique complexes of strongly regular graphs, and determine the spectra of the triangle complexes of several families of strongly regular graphs including Hamming graphs and Triangular graphs. In many cases, the spectrum of the triangle complex distinguishes between strongly regular graphs with the same parameters, but we find some examples where that is not the case. We also prove that if a graph has the property that for any induced cycle, there are four consecutive vertices on the cycle with a common neighbor, then the first cohomology group of the graph is trivial and we apply this result to several families of graphs.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- The theta number of simplicial complexesIsrael Journal of Mathematics, 2019
- Spectra of symmetric powers of graphs and the Weisfeiler–Lehman refinementsJournal of Combinatorial Theory, Series B, 2010
- Coined quantum walks lift the cospectrality of graphs and treesPattern Recognition, 2009
- Topology of random clique complexesDiscrete Mathematics, 2009
- Developments on spectral characterizations of graphsDiscrete Mathematics, 2009
- Symmetric squares of graphsJournal of Combinatorial Theory, Series B, 2007
- Topics in Algebraic Graph Theory, by Lowell W. Beineke and Robin J. Wilson (Academic Consultant: Peter J. Cameron), Encyclopedia of Mathematics and its Applications 102, CUP 2005, 257pp., £ 50.00/$95.00Combinatorics, Probability and Computing, 2006
- A Course in Combinatorics2001
- Algebraic Graph Theory2001
- The Clique Complex and Hypergraph MatchingCombinatorica, 2001