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

Clive Elphick; Mustapha Aouchiche

doi:10.1016/j.laa.2017.05.013

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

Clive Elphick, Mustapha Aouchiche

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

Terpai [21] proved the Nordhaus–Gaddum bound that μ(G)+μ(G‾)≤4n/3−1, where μ(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 s⁺(G)+s⁺(G‾)2n and conjecture that s⁺(G)+s⁺(G‾)≤4n/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ć index.

Original language	English
Pages (from-to)	150-159
Number of pages	10
Journal	Linear Algebra and Its Applications
Volume	530
DOIs	https://doi.org/10.1016/j.laa.2017.05.013
Publication status	Published - Oct 1 2017
Externally published	Yes

Keywords

Eigenvalues
Graph
Nordhaus–Gaddum relations
Randic index

ASJC Scopus subject areas

Algebra and Number Theory
Numerical Analysis
Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.laa.2017.05.013

Cite this

@article{c45cc7f8a2b942b6b567292267ba6b69,

title = "Nordhaus–Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph",

abstract = "Terpai [21] proved the Nordhaus–Gaddum bound that μ(G)+μ(G‾)≤4n/3−1, where μ(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 s+(G)+s+(G‾)2n and conjecture that s+(G)+s+(G‾)≤4n/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.",

keywords = "Eigenvalues, Graph, Nordhaus–Gaddum relations, Randic index",

author = "Clive Elphick and Mustapha Aouchiche",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier Inc.",

year = "2017",

month = oct,

day = "1",

doi = "10.1016/j.laa.2017.05.013",

language = "English",

volume = "530",

pages = "150--159",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

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

AU - Elphick, Clive

AU - Aouchiche, Mustapha

PY - 2017/10/1

Y1 - 2017/10/1

N2 - Terpai [21] proved the Nordhaus–Gaddum bound that μ(G)+μ(G‾)≤4n/3−1, where μ(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 s+(G)+s+(G‾)2n and conjecture that s+(G)+s+(G‾)≤4n/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ć index.

AB - Terpai [21] proved the Nordhaus–Gaddum bound that μ(G)+μ(G‾)≤4n/3−1, where μ(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 s+(G)+s+(G‾)2n and conjecture that s+(G)+s+(G‾)≤4n/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ć index.

KW - Eigenvalues

KW - Graph

KW - Nordhaus–Gaddum relations

KW - Randic index

UR - http://www.scopus.com/inward/record.url?scp=85019418420&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85019418420&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2017.05.013

DO - 10.1016/j.laa.2017.05.013

M3 - Article

AN - SCOPUS:85019418420

SN - 0024-3795

VL - 530

SP - 150

EP - 159

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this