Extrema of graph eigenvalues

DOI10.1016/J.LAA.2015.05.016MaRDI QIDQ492762zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 21 August 2015

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.00359

zbMATH Keywords

\(k\)th largest eigenvalue of a graph\(k\)th largest singular eigenvalue of a graphKy Fan norms of graphsspectral Nordhaus-Gaddum problems

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Abstract: In 1993 Hong asked what are the best bounds on the $k$'th largest eigenvalue $lambd{a}_k(G)$ of a graph $G$ of order $n$. This challenging question has never been tackled for any $2<k<n$. In the present paper tight bounds are obtained for all $k>2,$ and even tighter bounds are obtained for the $k$'th largest singular value $lambd{a}_k^{ast}(G).$ Some of these bounds are based on Taylor's strongly regular graphs, and other on a method of Kharaghani for constructing Hadamard matrices. The same kind of constructions are applied to other open problems, like Nordhaus-Gaddum problems of the kind: How large can $$ be$?$ These constructions are successful also in another open question: How large can the Ky Fan norm $lambd{a}_1^{ast}(G)+\mathrm{...}+lambd{a}_k^{ast}(G)$ be $?$ Ky Fan norms of graphs generalize the concept of graph energy, so this question generalizes the problem for maximum energy graphs. In the final section, several results and problems are restated for $(-1,1)$-matrices, which seem to provide a more natural ground for such research than graphs. Many of the results in the paper are paired with open questions and problems for further study.

Recommendations

• On the sum of \(k\) largest eigenvalues of graphs and symmetric matrices
• Eigenvalue problems of Nordhaus--Gaddum type
• On the sum of \(k\) largest singular values of graphs and matrices
• On the sum of the \(k\) largest eigenvalues of graphs and maximal energy of bipartite graphs
• Improved lower bounds on the extrema of eigenvalues of graphs

Cites work

• scientific article; zbMATH DE number 3935054 (Why is no real title available?)
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 4099367 (Why is no real title available?)
• scientific article; zbMATH DE number 3623599 (Why is no real title available?)
• scientific article; zbMATH DE number 635657 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• A survey of Nordhaus-Gaddum type relations
• An introduction to the theory of graph spectra
• Bounds of eigenvalues of graphs
• Bounds on graph eigenvalues
• Chromatic number and the 2-rank of a graph
• Combinatorics of symmetric designs
• Efficient testing of large graphs
• Eigenvalue problems of Nordhaus--Gaddum type
• Graph energy
• Graphs and matrices with maximal energy
• Linear combinations of graph eigenvalues
• Matrix Analysis
• Maximal energy graphs
• More eigenvalue problems of Nordhaus-Gaddum type
• On a conjecture of V. Nikiforov
• On the sum of \(k\) largest eigenvalues of graphs and symmetric matrices
• On the sum of \(k\) largest singular values of graphs and matrices
• On the sum of two largest eigenvalues of a symmetric matrix
• Proof of a conjecture of V. Nikiforov
• Pseudo-random graphs
• Quasi-random graphs
• Ramsey numbers, graph eigenvalues, and a conjecture of Cao and Yuan
• Regular 2-Graphs
• Strongly regular graphs with maximal energy
• Strongly regular graphs with parameters \((4m^{4},2m^{4}+m^{2},m^{4}+m^{2},m^{4}+m^{2})\) exist for all \(m>1\)
• The difference between consecutive primes. II
• The spread of the spectrum of a graph

Cited in

(21)

• On the sum of \(k\) largest singular values of graphs and matrices
• The clique number and the smallest \(Q\)-eigenvalue of graphs
• On the sum of \(k\) largest Laplacian eigenvalues of a graph and clique number
• A note on the relationship between graph energy and determinant of adjacency matrix
• Extreme eigenvalues of nonregular graphs
• Extremal Graph Realizations and Graph Laplacian Eigenvalues
• On the spectral radius, energy and estrada index of the arithmetic-geometric matrix of a graph
• Eigenvalues of subgraphs of the cube
• Improved lower bounds on the extrema of eigenvalues of graphs
• Graphs with few distinct eigenvalues and extremal energy
• Extremal eigenvalues of critical Erdős-Rényi graphs
• Maximum spread of graphs and bipartite graphs
• Extremal properties of eigenvalues for a metric graph.
• Symmetry and asymmetry between positive and negative square energies of graphs
• Further developments on Brouwer's conjecture for the sum of Laplacian eigenvalues of graphs
• On Laplacian eigenvalues of graphs and Brouwer's conjecture
• Beyond graph energy: norms of graphs and matrices
• Extremal norms of graphs and matrices
• On the Ky Fan $k$-norm of the $LI$-matrix of graphs
• On Zagreb index, signless Laplacian eigenvalues and signless Laplacian energy of a graph
• An inertial lower bound for the chromatic number of a graph

This page was built for publication: Extrema of graph eigenvalues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q492762)