A nontrivial upper bound on the largest Laplacian eigenvalue of weighted graphs
type: Item
instance of: scholarly article
title: A nontrivial upper bound on the largest Laplacian eigenvalue of weighted graphs
zbMATH Open document ID: 1110.05062
author: Oscar Rojo
published in: Linear Algebra and its Applications
publication date: 2007-01-09T00:00:00Z
review text: The author obtains an upper bound on the largest Laplacian eigenvalue of weighted graphs. Let \(G\) be a connected weighted graph on \(n\) vertices. The author denotes by \(w_{i,j}\) the weight of the edge \((i,j)\), \(i \sim j\) if the vertices \(i\) and \(j\) are adjacent and \(w_i=\sum_{i \sim j} w_{k,i}\). He also denotes by \(L(G)\) the Laplacian matrix of \(G\) and \(\lambda_1 \geq \lambda_2 \geq \cdots \lambda_{n-1}>\lambda_n=0\) the eigenvalues of \(L(G)\). The main result of the paper establishes the following upper bound on the largest Laplacian eigenvalue: \[ \lambda_1 \leq \tfrac{1}{2}\max_{i \sim j} \left\{w_i+w_j+ \sum_{k \sim i, k \not \sim j}w_{i,k}+ \sum_{k \sim j, k \not \sim i}w_{j,k}+ \sum_{k \sim i, k \not \sim j} | w_{i,k}-w_{j,k}| \right\}. \] This upper bound does not exceed \(\sum_{j=1}^n \max_{k \sim j} w_{k,j}\).
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 15A18
zbMATH DE Number: 5083630
zbMATH Keywords: Laplacian matrix
zbMATH Keywords: spectral radius
reviewed by: Juan Ramón Torregrosa Sánchez
MaRDI profile type: MaRDI publication profile
full work available at URL: j.laa.2006.08.022
OpenAlex ID: W2136339442
cites work: Laplacian matrices of graphs: A survey
cites work: Eigenvalues of the Laplacian of a graph∗
cites work: An improved upper bound for Laplacian graph eigenvalues
cites work: A characterization on graphs which achieve the upper bound for the largest Laplacian eigenvalue of graphs.
cites work: The Laplacian Spectrum of a Graph II
cites work: A new upper bound for eigenvalues of the Laplacian matrix of a graph
cites work: On the Laplacian eigenvalues of a graph
cites work: de Caen's inequality and bounds on the largest Laplacian eigenvalue of a graph
cites work: An always nontrivial upper bound for Laplacian graph eigenvalues
cites work: Bounds for sums of eigenvalues and applications
cites work: Limits for the characteristic roots of a matrix. IV. Applications to stochastic matrices
cites work: Abschätzungen für die Eigenwerte positiver linearer Operatoren
cites work: A sharp upper bound on the largest Laplacian eigenvalue of weighted graphs
DOI: 10.1016/J.LAA.2006.08.022
description: scientific article; zbMATH DE number 5083630