Least eigenvalue of the connected graphs whose complements are cacti

Abstract

Suppose that Γ is a graph of order n and A(Γ) = [ai,j] is its adjacency matrix such that ai,j is equal to 1 if vi is adjacent to vj and ai,j is zero otherwise, where 1 ≤ i, j ≤ n. In a family of graphs, a graph is called minimizing if the least eigenvalue of its adjacency matrix is minimum in the set of the least eigenvalues of all the graphs. Petrović et al. [On the least eigenvalue of cacti, Linear Algebra Appl., 2011, 435, 2357-2364] characterized a minimizing graph in the family of all cacti such that the complement of this minimizing graph is disconnected. In this paper, we characterize the minimizing graphs G ∈ Ωnc$\begin{array}{} {\it\Omega}^c_n \end{array}$, i.e.

Keywords

• adjacency matrix
• least eigenvalue
• connected graphs
• cacti
• 15a18
• 05c50
• 05c40
• 05d05