On Two Conjectures of Spectral Graph Theory.

Let G=(V,E)<inline-graphic></inline-graphic> be a simple graph. Denote by <italic>D</italic>(<italic>G</italic>) the diagonal matrix of its vertex degrees and by <italic>A</italic>(<italic>G</italic>) its adjacency matrix. Then the Laplacian matrix and the signless Laplacian matrix of <italic>G</italic> are L(G)=D(G)-A(G)<inline-graphic></inline-graphic> and Q(G)=D(G)+A(G)<inline-graphic></inline-graphic>, respectively. Also denote by λ1(G)<inline-graphic></inline-graphic>, <italic>a</italic>(<italic>G</italic>), q1(G)<inline-graphic></inline-graphic> and δ(G)<inline-graphic></inline-graphic> the largest eigenvalue of <italic>A</italic>(<italic>G</italic>), the second smallest eigenvalue of <italic>L</italic>(<italic>G</italic>), the largest eigenvalue of <italic>Q</italic>(<italic>G</italic>) and the minimum degree of <italic>G</italic>, 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, <xref>2006</xref>) if <italic>G</italic> is a connected graph, then a(G)/δ(G)<inline-graphic></inline-graphic> is minimum for graph composed of 2 triangles linked with a path. (ii)Aouchiche et al. (Linear Algebra Appl 432:2293-2322, <xref>2010</xref>) and Cvetković et al. (Publ Inst Math Beogr 81(95):11-27, <xref>2007</xref>) if <italic>G</italic> is a connected graph with n≥4<inline-graphic></inline-graphic> vertices, then q1(G)-2λ1(G)≤n-2n-1<inline-graphic></inline-graphic> with equality holding if and only if G≅K1,n-1<inline-graphic></inline-graphic>. [ABSTRACT FROM AUTHOR]