Maximum norms of graphs and matrices, and their complements

Given a graph G, let ∥ G ∥+ denote the trace norm of its adjacency matrix, also known as the energy of G. The main result of this paper states that if G is a graph of order n, then ∥G∥ + ∥ Ḡ∥+ ≤ (n-1)(1+√n),where Ḡ is the complement of G. Equality is possible if and only if G is a strongly regular graph with parameters n,n-1/2,n-5/4,n-1/4, known also as a conference graph. In fact, the above problem is stated and solved in a more general setup - for nonnegative matrices with bounded entries. In particular, this study exhibits analytical matrix functions attaining maxima on matrices with rigid and complex combinatorial structure. In the last section the same questions are studied for Ky Fan norms. Possibe directions for further research are outlined, as it turns out that the above problems are just a tip of a larger multidimensional research area. © 2013 Elsevier Inc. All rights reserved