On the normalized Laplacian spectral radii of a graph and its line graph
- PDF / 428,959 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 212 Views
On the normalized Laplacian spectral radii of a graph and its line graph Shaowei Sun1 · Kinkar Chandra Das2 Received: 5 June 2020 / Revised: 23 September 2020 / Accepted: 25 September 2020 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2020
Abstract Normalized Laplacian eigenvalues are very popular in spectral graph theory. The normalized Laplacian spectral radius ρ1 (G) of a graph G is the largest eigenvalue of normalized Laplacian matrix of G. In this paper, we determine the extremal graph for the minimum normalized Laplacian spectral radii of nearly complete graphs. We present several lower bounds on ρ1 (G) in terms of graph parameters and characterize the extremal graphs. Still, there is no result on the normalized Laplacian eigenvalues of line graphs. Here, we obtain sharp lower bounds on the normalized Laplacian spectral radii of line graphs. Moreover, we compare ρ1 (G) and ρ1 (L G ) (L G is the line graph of G) in some class of graphs as they are incomparable in the general case. Finally, we present a relation on the normalized Laplacian spectral radii of a graph and its line graph. Keywords Normalized Laplacian spectral radius · Line graph · Nearly complete graph · Independence number · Bipartite edge frustration Mathematics Subject Classification 05C50 · 15A18
1 Introduction Let G = (V (G), E(G)) be a simple graph without isolated vertices, whose vertex set is V (G) = {v1 , v2 , . . . , vn } and edge set is E(G). Also, let dG (vi ) denote the degree of a vertex vi ∈ V (G), i = 1, 2, . . . , n. The maximum degree and the minimum degree of G are denoted by (G) and δ(G), respectively. Let N G (vi ) be the neighbor set of the vertex
Communicated by Carlos Hoppen.
B
Kinkar Chandra Das [email protected] Shaowei Sun [email protected]
1
School of Science, Zhejiang University of Science and Technology, Hangzhou 310023, Zhejiang, People’s Republic of China
2
Department of Mathematics, Sungkyunkwan University, Suwon 16419, Republic of Korea 0123456789().: V,-vol
123
283
Page 2 of 15
S. Sun, K.C. Das
vi ∈ V (G). If the vertices vi and v j are adjacent, we write vi v j ∈ E(G). For a subset E of E(G), G − E is a subgraph of G obtained by deleting the edges in E . Let S ⊂ V (G) be any subset of vertices of graph G. Then the induced subgraph G[S] is the graph whose vertex set is S and whose edge set consists of all of edges in E(G) that have both endpoints in S. The join G 1 G 2 of graphs G 1 and G 2 is the graph obtained from the disjoint union of G 1 and G 2 by adding all edges between V (G 1 ) and V (G 2 ). We say a graph G is a (s, t)-semiregular graph if any vertex of G has degree s or t. We use G to denote the complement of the graph G. The Laplacian matrix L(G) is defined as D(G)− A(G), where D(G) is the diagonal matrix of vertex degrees of G and A(G) is the adjacency matrix of graph G. Then the normalized Laplacian matrix of the graph G is defined as L(G) = D −1/2 (G)L(G)D −1/2 (G), whose eigenvalues are denoted by ρ1 (G) ≥ ρ2 (G) ≥ · · · ≥ ρn−1 (G) ≥ ρn (G) = 0.
Data Loading...
