2013/11/29 by Bojana Mihailović, Bojana Mihailovic, Mihailovic, Bojana +3
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #math.CO
paper · pdf · doi:10.48550/arxiv.1311.7515
arxiv created 2013/11/29 · openalex publication_date 2013/11/29 · arxiv updated 2013/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Eigenvalues of a graph are the eigenvalues of the corresponding (0,1)-adjacency matrix. The second largest eigenvalue lambda2 provides significant information on characteristics and structure of graphs. Therefore, finding bounds for lambda2 is a topic of interest in many fields. So far we have studied the graphs with the property lambda2 is less or equal to 2, so-called reflexive graphs. The original RS-theorem is about them. In this paper we generalize that concept and introduce the arbitrary bounds. The Generalized RS-theorem gives us an answer whether the second largest eigenvalue of a graph is greater than, less than, or equal to a, a>0, within some classes of connected graphs with a cut-vertex. After removing the cut-vertex u of the given graph G, we examine the indices of the components of G-u. The information on these indices is used to make conclusions about the second largest eigenvalue of the graph G. In the RS-theorem a=2. Here, we state and prove the Generalized RS-theorem, one corollary, and, also, give some useful lemmas.