4.5 Article

Lower bounds for the spectral norm of digraphs

Journal

LINEAR ALGEBRA AND ITS APPLICATIONS
Volume 617, Issue -, Pages 151-167

Publisher

ELSEVIER SCIENCE INC
DOI: 10.1016/j.laa.2021.01.008

Keywords

Spectral norm of digraphs; Spectral radius of digraphs; Almost regular digraphs; Splitting digraphs; Trace norm of digraphs

Ask authors/readers for more resources

This paper explores the spectral and trace norms of digraphs, providing lower bounds and introducing the concept of almost regular digraphs. It also gives new upper bounds for the trace norm of digraphs and identifies the digraphs for which these bounds are optimal, such as sink-source complete bipartite digraphs or symmetric balanced incomplete block designs.
Let D be a digraph with n vertices and sigma(1) (D) >= sigma(2) (D) >= ... >= sigma(n) (D) the singular values of the adjacency matrix A of D. The spectral norm of D is sigma(1) (D) and the trace norm of D is parallel to D parallel to(*) = Sigma(n)(i=1) sigma(i) (D). In this paper we find lower bounds for the spectral norm of a digraph in terms of the structure of the digraph. Moreover, we introduce the concept of almost regular digraphs (extension of the well known almost regular graphs), and show that the lower bounds are attained precisely in almost regular digraphs. When we apply this theory to graphs, we recover well known lower bounds for the spectral radius of graphs. Also, we give a new upper bound for the trace norm of a digraph. Moreover, we determine the digraphs for which this bound is sharp: sink-source complete bipartite digraphs or symmetric balanced incomplete block designs (BIBD). (C) 2021 Elsevier Inc. All rights reserved.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available