Bounds for the Largest Laplacian Eigenvalue of Weighted Graphs

Let be weighted graphs, as the graphs where the edge weights are positive definite matrices. The Laplacian eigenvalues of a graph are the eigenvalues of Laplacian matrix of a graph . We obtain two upper bounds for the largest Laplacian eigenvalue of weighted graphs and we compare these bounds with previously known bounds. 1. Introduction Let be simple graphs, as graphs which have no loops or parallel edges such that is a finite set of vertices and is a set of edges. A weighted graph is a graph each edge of which has been assigned to a square matrix called the weight of the edge. All the weight matrices are assumed to be of same order and to be positive matrix. In this paper, by “weighted graph” we mean “a weighted graph with each of its edges bearing a positive definite matrix as weight,” unless otherwise stated. The notations to be used in paper are given in the following. Let be a weighted graph on vertices. Denote by the positive definite weight matrix of order of the edge , and assume that . We write if vertices and are adjacent. Let . be the weight matrix of the vertex . The Laplacian matrix of a graph is defined as , where The zero denotes the zero matrix. Hence is square matrix of order . Let denote the largest eigenvalue of . In this paper we also use to avoid the confusion that is the spectral radius of matrix. If is the disjoint union of two nonempty sets and such that every vertex in has the same and every vertex in has the same , then is called a weight-semiregular graph. If in weight semiregular graph, then is called a weighted-regular graph. Upper and lower bounds for the largest Laplacian eigenvalue for unweighted graphs have been investigated to a great extent in the literature. Also there are some studies about the bounds for the largest Laplacian eigenvalue of weighted graphs [1–3]. The main result of this paper, contained in Section 2, gives two upper bounds on the largest Laplacian for weighted graphs, where the edge weights are positive definite matrices. These upper bounds are attained by the same methods in [1–3]. We also compare the upper bounds with the known upper bounds in [1–3]. We also characterize graphs which achieve the upper bound. The results clearly generalize some known results for weighted and unweighted graphs. 2. The Known Upper Bounds for the Largest Laplacian Eigenvalue of Weighted Graphs In this section, we present the upper bounds for the largest Laplacian eigenvalue of weighted graphs and very useful lemmas to prove theorems. Theorem 1 (Horn and Johnson [4]). Let be Hermitian, and let the eigenvalues of be