Upper Bounds on the (Signless Laplacian) Spectral Radius of Irregular Weighted Graphs
- PDF / 381,275 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 97 Downloads / 169 Views
Upper Bounds on the (Signless Laplacian) Spectral Radius of Irregular Weighted Graphs Shuiqun Xie1 · Xiaodan Chen1
· Xiuyu Li1 · Xiaoqian Liu1
Received: 11 July 2020 / Revised: 31 October 2020 / Accepted: 9 November 2020 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2020
Abstract In this paper, we consider simple connected weighted graphs in which the edge weights are positive numbers. We obtain several upper bounds on the spectral radius and the signless Laplacian spectral radius of irregular weighted graphs, which extend some known results for irregular unweighted graphs. Keywords Irregular weighted graph · Spectral radius · Signless Laplacian spectral radius · Upper bound Mathematics Subject Classification 05C50
1 Introduction Throughout this paper, we consider simple weighted graphs in which the edge weights are positive numbers. Let G be such a graph with vertex set V (G) = {v1 , v2 , . . . , vn } the weight of the edge vi v j and assume that and edge set E(G). Denote by wi j wi j = w ji . For vi ∈ V (G), let wi = v j ∈NG (vi ) wi j , where N G (vi ) is the set of the neighbours of vi in G. A graph G is called regular if wi = w j for any two vertices vi , v j ∈ V (G). The distance between two distinct vertices vi , v j ∈ V (G), denoted by dG (vi , v j ), is the length of a shortest path between them. The diameter of G, denoted by diam(G), is the maximum distance between any two vertices of G. The adjacency matrix of a graph G is defined as A(G) = (ai j )n×n , where ai j =
wi j if vi v j ∈ E(G); 0 otherwise.
Communicated by Xueliang Li.
B 1
Xiaodan Chen [email protected] College of Mathematics and Information Science, Guangxi University, Nanning, China
123
S. Xie et al.
The signless Laplacian matrix of a graph G is Q(G) = W (G)+ A(G), where W (G) = diag(w1 , w2 , . . . , wn ). It is easy to see that A(G) and Q(G) are real symmetric matrices, and hence, their eigenvalues are real numbers. Here, we focus on the largest eigenvalues of A(G) and Q(G), which are also referred to as the spectral radius and the signless Laplacian spectral radius of G and are denoted by λ1 (G) and q1 (G), respectively. If G is connected, then we know that A(G) and Q(G) are nonnegative irreducible matrices. By the Perron–Frobenius theorem (see, e.g. [8]), we have λ1 (G) and q1 (G) are simple with positive eigenvectors. Another classical result in the theory of nonnegative matrices (see, e.g. [8]) states that for any nonnegative irreducible n × n matrix M with the largest eigenvalue ρ(M) and row sums S1 , S2 , . . . , Sn , min Si ≤ ρ(M) ≤ max Si ,
1≤i≤n
1≤i≤n
where either equality holds if and only if the row sums of M are all equal. Now, by applying this result to A(G) and Q(G) for a simple connected weighted graph G of order n, respectively, we have min wi ≤ λ1 (G) ≤ max wi
(1)
2 min wi ≤ q1 (G) ≤ 2 max wi ,
(2)
1≤i≤n
1≤i≤n
and 1≤i≤n
1≤i≤n
where either equality holds in both inequalities if and only if G is regular. For some other upper and lower bounds on λ1 (G) and q1 (G) fo
Data Loading...
