A spectral bound for vertex-transitive graphs and their spanning subgraphs

Arindam Biswas, Jyoti Prakash Saha

Abstract

For any finite, undirected, non-bipartite, vertex-transitive graph, we establish an explicit lower bound for the smallest eigenvalue of its normalised adjacency operator, which depends on the graph only through its degree and its vertex-Cheeger constant. We also prove an analogous result for a large class of irregular graphs, obtained as spanning subgraphs of vertex-transitive graphs. Using a result of Babai, we obtain a lower bound for the smallest eigenvalue of the normalised adjacency operator of a vertex-transitive graph in terms of its diameter and its degree.
BibTeX
@inproceedings{biswas2023spectral,
  author = {Arindam Biswas and Jyoti Prakash Saha},
  title = {{A spectral bound for vertex-transitive graphs and their spanning subgraphs}},
  booktitle = {Algebraic Combinatorics},
  year = {2023},
  doi = {10.5802/alco.278},
}

Loading related content...

Figure