On the least eigenvalue of genuine strongly 3-walk-regular graphs.

As a generalization of strongly regular graphs, van Dam and Omidi [8] introduced the concept of strongly walk-regular graphs. A graph is called strongly ℓ -walk-regular if the number of walks of length ℓ from a vertex to another vertex depends only on whether the two vertices are adjacent, not adjacent, or identical. They proved that this class of graphs falls into several subclasses including connected regular graphs with four eigenvalues, which are called genuine strongly ℓ -walk-regular. In this paper, we prove that the least eigenvalue of a connected genuine strongly 3-walk-regular graph is no more than −2 and characterize all graphs reaching this upper bound. • We focus on the problem that the existence of strongly ℓ -walk-regular graphs which are not strongly 3-walk-regular. This problem is natural and important. • We prove that the least eigenvalue of a connected genuine strongly 3-walk-regular graph is no more than -2 and characterize all graphs reaching this upper bound. • The problem of determining the graphs with least eigenvalue -2 was one of the first challenges in the theory of graph spectra, and most proof of this problem was difficult. The proof of our main result is concise and easy to understand. [ABSTRACT FROM AUTHOR]