Spectral conditions for connectivity, toughness and perfect \(k\)-matchings of regular graphs (Q2699581)

This paper provides bounds that relate the second largest eigenvalue of a \(d\)-regular graph with certain graph parameters such as the edge- and vertex- connectivity and the toughness as well as the existence of perfect \(k\)-matchings. The first result provides upper bounds on the second largest eigenvalue of a connected \(d\)-regular graph with \(d\geq 3\), which imply that the connectivity is at least as large as \(\ell +1\), for \(1\leq \ell \leq d-1\). The second result provides a lower bound on the second largest eigenvalue of \(G\) (under the above assumptions) if it has a cut set of size at most 2. The author shows that the lower bound is sharp, constructing a graph for which this bound is attained. The third result provides a lower bound on the toughness of \(G\) in terms of \(d\), the second largest and the smallest eigenvalue of the adjacency matrix. The final theorem gives a sufficient condition for the existence of a perfect \(k\)-matching in \(G\). A perfect \(k\)-matching is an assignment of numbers from the set \(\{0,\ldots ,k-1\}\) to the edges of \(G\) such that for each vertex the sum of the values of this assignment on the edges incident to this vertex is \(k\). (A perfect 1-matching, in particular, is a perfect matching.) The condition is an upper bound on a certain eigenvalue of the adjacency matrix, whose index depends on \(k\).