Back to Search
Start Over
Proof of conjecture involving algebraic connectivity and average degree of graphs.
- Source :
-
Linear Algebra & its Applications . Jul2018, Vol. 548, p172-188. 17p. - Publication Year :
- 2018
-
Abstract
- Let G be a simple connected graph of order n with m edges. Denote by D ( G ) the diagonal matrix of its vertex degrees and by A ( G ) its adjacency matrix. Then the Laplacian matrix of graph G is L ( G ) = D ( G ) − A ( G ) . Among all eigenvalues of the Laplacian matrix L ( G ) of graph G , the most studied is the second smallest, called the algebraic connectivity a ( G ) of a graph. Let d ‾ ( G ) and δ ( G ) be the average degree and the minimum degree of graph G , respectively. In this paper we characterize all graphs for which ( i ) a ( G ) = 1 with δ ( G ) ≥ ⌈ n − 1 2 ⌉ , and ( i i ) a ( G ) = 2 with δ ( G ) ≥ n 2 . In [1] , Aouchiche mentioned a conjecture involving the algebraic connectivity a ( G ) and the average degree d ‾ ( G ) of graph G : a ( G ) − d ‾ ( G ) ≥ 4 − n − 4 n with equality holding if and only if G ‾ ≅ K 1 , n − 2 ∪ K 1 ( K 1 , n − 2 is a star of order n − 1 and G ‾ is the complement of graph G ). Here we prove this conjecture. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00243795
- Volume :
- 548
- Database :
- Academic Search Index
- Journal :
- Linear Algebra & its Applications
- Publication Type :
- Academic Journal
- Accession number :
- 128922923
- Full Text :
- https://doi.org/10.1016/j.laa.2018.03.006