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

DOI10.1016/J.LAA.2017.05.013zbMATH Open1367.05127arXiv1607.08258OpenAlexW2963702568MaRDI QIDQ2013183FDOQ2013183

Authors: Clive Elphick, Mustapha Aouchiche 

Publication date: 3 August 2017

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

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.

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

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

zbMATH Keywords

eigenvaluesRandic indexNordhaus-Gaddum relations

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

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

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)