More eigenvalue problems of Nordhaus-Gaddum type

DOI10.1016/J.LAA.2014.03.024MaRDI QIDQ2451210zbMATH OpenOpenAlexFDO

Authors Vladimir Nikiforov, Xiying Yuan

Publication date 3 June 2014

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

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

zbMATH Keywords

complementary graphgraph eigenvaluesmaximum eigenvalueminimum eigenvalueNordhaus-Gaddum problems

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42)

Abstract: Let $G$ be a graph of order $n$ and let $m{u}_{1}left(Gight)geqcdotsgeqm{u}_{n}left(Gight)$ be the eigenvalues of its adjacency matrix. This note studies eigenvalue problems of Nordhaus-Gaddum type. Let $overlineG$ be the complement of a graph $G.$ It is shown that if $sgeq2$ and $ngeq15left(s-1ight),$ then [ leftvert mu_{s}left(G ight) ightvert +|mu_{s}(overline{G})|,leq n/sqrt{2left(s-1 ight)}-1. ] Also if $sgeq1$ and $ngeq{4}^s,$ then [ leftvert mu_{n-s+1}left(G ight) ightvert +|mu_{n-s+1}(overline {G})|,leq n/sqrt{2s}+1. ] If $s=2^k+1$ for some integer $k$, these bounds are asymptotically tight. These results settle infinitely many cases of a general open problem.

Recommendations

• Eigenvalue problems of Nordhaus--Gaddum type
• A note on the Nordhaus-Gaddum type inequality to the second largest eigenvalue of a graph
• Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph
• A sharp upper bound for the spectral radius of the Nordhaus-Gaddum type
• Signless Laplacian eigenvalue problems of Nordhaus-Gaddum type

Cites work

• A survey of Nordhaus-Gaddum type relations
• Eigenvalue problems of Nordhaus--Gaddum type
• Eigenvalues and degree deviation in graphs
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Matrix Analysis
• On a conjecture of V. Nikiforov
• On Complementary Graphs
• Proof of a conjecture of V. Nikiforov
• Upper Bounds on the Order of a Clique of a Graph

Cited in

(17)

• On a conjecture of V. Nikiforov
• A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
• A sharp upper bound for the spectral radius of the Nordhaus-Gaddum type
• Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph
• Nordhaus-Gaddum type inequalities of the second \(A_\alpha\)-eigenvalue of a graph
• Signless Laplacian eigenvalue problems of Nordhaus-Gaddum type
• Nordhaus-Gaddum type inequalities for the two largest Laplacian eigenvalues
• Proof of a conjecture of V. Nikiforov
• Some Nordhaus-Gaddum type results of \(A_\alpha \)-eigenvalues of weighted graphs
• Note on Nordhaus-Gaddum problems for Colin de Verdière type parameters
• Extrema of graph eigenvalues
• A note on the Nordhaus-Gaddum type inequality to the second largest eigenvalue of a graph
• Products of graphs and Nordhaus-Gaddum type inequalities for eigenvalues
• Generalizations of some Nordhaus–Gaddum‐type results on spectral radius
• Nordhaus-Gaddum type inequalities for the \(k\)th largest Laplacian eigenvalues
• A conjecture on the Nordhaus-Gaddum product type inequality for Laplacian eigenvalue of a graph
• Eigenvalue problems of Nordhaus--Gaddum type

This page was built for publication: More eigenvalue problems of Nordhaus-Gaddum type

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