Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph

DOI10.1016/J.LAA.2017.05.013MaRDI QIDQ2013183zbMATH OpenOpenAlexFDO

Authors Clive Elphick, Mustapha Aouchiche

Publication date 3 August 2017

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

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

zbMATH Keywords

eigenvaluesRandic indexNordhaus-Gaddum relations

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Terpai [22] proved the Nordhaus-Gaddum bound that $mu(G)+mu(overlineG)le4n/3-1$, where $mu(G)$ is the spectral radius of a graph $G$ with $n$ vertices. Let $s^{+}$ denote the sum of the squares of the positive eigenvalues of $G$. We prove that $sqrt{s}^{+}(G)+sqrt{s}^{+}(overlineG)<sqrt2n$ and conjecture that $sqrt{s}^{+}(G)+sqrt{s}^{+}(overlineG)le4n/3-1.$ We have used AutoGraphiX and Wolfram Mathematica to search for a counter-example. We also consider Nordhaus-Gaddum bounds for $s^{+}$ and bounds for the Randi'c index.

Recommendations

• Conjectured bounds for the sum of squares of positive eigenvalues of a graph
• More eigenvalue problems of Nordhaus-Gaddum type
• A sharp upper bound for the spectral radius of the Nordhaus-Gaddum type
• Nordhaus-Gaddum type inequalities for the two largest Laplacian eigenvalues
• Eigenvalue problems of Nordhaus--Gaddum type

Cites work

• scientific article; zbMATH DE number 3253789 (Why is no real title available?)
• scientific article; zbMATH DE number 3394189 (Why is no real title available?)
• A bound on the spectral radius of graphs with \(e\) edges
• A survey of Nordhaus-Gaddum type relations
• Conjectured bounds for the sum of squares of positive eigenvalues of a graph
• Eigenvalue problems of Nordhaus--Gaddum type
• Maximum norms of graphs and matrices, and their complements
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• On Complementary Graphs
• On a conjecture of V. Nikiforov
• Open problems on graph eigenvalues studied with AutoGraphiX
• Proof of a conjecture of V. Nikiforov
• Proof of a conjectured lower bound on the chromatic number of a graph
• Some Inequalities for the Largest Eigenvalue of a Graph
• Some eigenvalue properties in graphs (conjectures of Graffiti -- II)
• Upper Bounds on the Order of a Clique of a Graph
• Upper bounds for the achromatic and coloring numbers of a graph
• Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph
• Variable neighborhood search for extremal graphs. I: The AutoGraphiX system
• Variable neighborhood search for extremal graphs. V: Three ways to automate finding conjectures
• Variable neighborhood search for extremal graphs. XIV: The AutoGraphiX 2 system

Cited in

(6)

• More eigenvalue problems of Nordhaus-Gaddum type
• Some Nordhaus-Gaddum type results of \(A_\alpha \)-eigenvalues of weighted graphs
• The estimation of the bound of the sum of squares of positive (negative) eigenvalues of a graph
• Generalizations of some Nordhaus–Gaddum‐type results on spectral radius
• Conjectured bounds for the sum of squares of positive eigenvalues of a graph
• Graph Limits and Spectral Extremal Problems for Graphs

Describes a project that uses

Uses Software

• Mathematica
• AutoGraphiX

This page was built for publication: Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph

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