Eigenvalue Bounds for Some Classes of Matrices Associated with Graphs
- PDF / 174,776 Bytes
- 21 Pages / 499 x 709 pts Page_size
- 2 Downloads / 235 Views
21 pp
Czechoslovak Mathematical Journal
Online first
EIGENVALUE BOUNDS FOR SOME CLASSES OF MATRICES ASSOCIATED WITH GRAPHS Ranjit Mehatari, Rourkela, M. Rajesh Kannan, Kharagpur Received July 1, 2019. Published online September 21, 2020.
Abstract. For a given complex square matrix A with constant row sum, we establish two new eigenvalue inclusion sets. Using these bounds, first, we derive bounds for the second largest and the smallest eigenvalues of adjacency matrices of k-regular graphs. Then we establish some bounds for the second largest and the smallest eigenvalues of the normalized adjacency matrices of graphs and the second smallest and the largest eigenvalues of the Laplacian matrices of graphs. The sharpness of these bounds is verified by examples. Keywords: adjacency matrix; Laplacian matrix; normalized adjacency matrix; spectral radius; algebraic connectivity; Randi´c index MSC 2020 : 05C50
1. Introduction In this paper we consider simple, connected, finite and undirected graphs. Let G = (V, E) be a graph with the vertex set V = {1, 2, . . . , n} and the edge set E. If two vertices i and j of G are adjacent, we denote it by i ∼ j. For each vertex i let di denote the degree of the vertex i. A graph is said to be d-regular if di = d for all i. n P di /n. A vertex i is The average degree of a graph G, denoted by ∆, defined as i=1
said to be a dominating vertex if it is adjacent to all other vertices, i.e. di = n − 1. We use N (i, j) to denote the number of common neighbors of the vertices i, j ∈ V , i 6= j. For more of graph theoretic terminology we refer to [3].
Ranjit Mehatari is funded by NPDF (File no: PDF/2017/001312), SERB, Department of Science and Technology, India. M. Rajesh Kannan would like to thank SERB, Department of Science and Technology, India for the financial support (Early Career Research Award (ECR/2017/000643)). DOI: 10.21136/CMJ.2020.0290-19
1
The (0, 1)-adjacency matrix A = [aij ] of a graph G, on n vertices, is an n × n matrix defined by ( 1 if i ∼ j, aij = 0 otherwise. Let D denote the diagonal matrix whose (i, i)th entry is di . Then the matrix L = D − A is called the Laplacian matrix of the graph G, and the matrix A = D−1 A is called the normalized adjacency matrix (or the transition matrix) of G . For more details we refer to [5], [8], [9]. The matrix A is similar to the Randi´c matrix, see [4]. For any real number α, the general Randi´c index Rα (G) of G (see [2], [14]) is defined by X α Rα (G) = dα i dj . i∼j
All the matrices A, L and A have real eigenvalues and reflect various interesting properties of the underlying graph G. Each of them comes with a set of strengths and weaknesses, which are discussed elaborately in [6]. Various bounds for the normalized adjacency matrix of a graph can be found in [1], [8], [12], [15]. In [16], the author surveys eigenvalue bounds for different types of matrices associated with a graph, viz. adjacency matrix, Laplacian matrix, signless Laplacian matrix, etc. In this paper, we provide some new bounds for the eigenvalues of adjacency
Data Loading...
