On Two Conjectures of Spectral Graph Theory

Let G=(V,E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the Laplacian matrix and the signless Laplacian matrix of G are L(G) = D(G) - A(G) and Q(G) = D(G) + A(G) , respectively. Also denote by λ₁(G) , a(G), q₁(G) and δ(G) the largest eigenvalue of A(G), the second smallest eigenvalue of L(G), the largest eigenvalue of Q(G) and the minimum degree of G, respectively. In this paper, we give partial proofs to the following two conjectures: (i)Aouchiche (Comparaison Automatisée d’Invariants en Théorie des Graphes, 2006) if G is a connected graph, then a(G) / δ(G) is minimum for graph composed of 2 triangles linked with a path.(ii)Aouchiche et al. (Linear Algebra Appl 432:2293–2322, 2010) and Cvetković et al. (Publ Inst Math Beogr 81(95):11–27, 2007) if G is a connected graph with n≥ 4 vertices, then q1(G)-2λ1(G)≤n-2n-1 with equality holding if and only if G≅ K_{1 , n - 1}.