Back to Search
Start Over
On Two Conjectures of Spectral Graph Theory.
- Source :
-
Bulletin of the Iranian Mathematical Society . Feb2018, Vol. 44 Issue 1, p43-51. 9p. - Publication Year :
- 2018
-
Abstract
- 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]
Details
- Language :
- English
- ISSN :
- 10186301
- Volume :
- 44
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Bulletin of the Iranian Mathematical Society
- Publication Type :
- Academic Journal
- Accession number :
- 129409186
- Full Text :
- https://doi.org/10.1007/s41980-018-0003-3