Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph

M. Aouchiche; F. K. Bell; D. Cvetković; P. Hansen; P. Rowlinson; S. K. Simić; D. Stevanović

doi:10.1016/j.ejor.2006.12.059

Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph

M. Aouchiche, F. K. Bell, D. Cvetković, P. Hansen, P. Rowlinson, S. K. Simić, D. Stevanović

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

33 Citations (Scopus)

Abstract

We consider four conjectures related to the largest eigenvalue of (the adjacency matrix of) a graph (i.e., to the index of the graph). Three of them have been formulated after some experiments with the programming system AutoGraphiX, designed for finding extremal graphs with respect to given properties by the use of variable neighborhood search. The conjectures are related to the maximal value of the irregularity and spectral spread in n-vertex graphs, to a Nordhaus-Gaddum type upper bound for the index, and to the maximal value of the index for graphs with given numbers of vertices and edges. None of the conjectures has been resolved so far. We present partial results and provide some indications that the conjectures are very hard.

Original language	English
Pages (from-to)	661-676
Number of pages	16
Journal	European Journal of Operational Research
Volume	191
Issue number	3
DOIs	https://doi.org/10.1016/j.ejor.2006.12.059
Publication status	Published - Dec 16 2008
Externally published	Yes

Keywords

Adjacency matrix
AutoGraphiX
Conjectures
Extremal graph
Graph
Index
Irregularity
Largest eigenvalue
Spectral spread
Variable neighborhood search

ASJC Scopus subject areas

Computer Science(all)
Modelling and Simulation
Management Science and Operations Research
Information Systems and Management

Access to Document

10.1016/j.ejor.2006.12.059

Cite this

@article{febb4df9b5a14ca7a3774a6120327bc2,

title = "Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph",

abstract = "We consider four conjectures related to the largest eigenvalue of (the adjacency matrix of) a graph (i.e., to the index of the graph). Three of them have been formulated after some experiments with the programming system AutoGraphiX, designed for finding extremal graphs with respect to given properties by the use of variable neighborhood search. The conjectures are related to the maximal value of the irregularity and spectral spread in n-vertex graphs, to a Nordhaus-Gaddum type upper bound for the index, and to the maximal value of the index for graphs with given numbers of vertices and edges. None of the conjectures has been resolved so far. We present partial results and provide some indications that the conjectures are very hard.",

keywords = "Adjacency matrix, AutoGraphiX, Conjectures, Extremal graph, Graph, Index, Irregularity, Largest eigenvalue, Spectral spread, Variable neighborhood search",

author = "M. Aouchiche and Bell, {F. K.} and D. Cvetkovi{\'c} and P. Hansen and P. Rowlinson and Simi{\'c}, {S. K.} and D. Stevanovi{\'c}",

year = "2008",

month = dec,

day = "16",

doi = "10.1016/j.ejor.2006.12.059",

language = "English",

volume = "191",

pages = "661--676",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph

AU - Aouchiche, M.

AU - Bell, F. K.

AU - Cvetković, D.

AU - Hansen, P.

AU - Rowlinson, P.

AU - Simić, S. K.

AU - Stevanović, D.

PY - 2008/12/16

Y1 - 2008/12/16

N2 - We consider four conjectures related to the largest eigenvalue of (the adjacency matrix of) a graph (i.e., to the index of the graph). Three of them have been formulated after some experiments with the programming system AutoGraphiX, designed for finding extremal graphs with respect to given properties by the use of variable neighborhood search. The conjectures are related to the maximal value of the irregularity and spectral spread in n-vertex graphs, to a Nordhaus-Gaddum type upper bound for the index, and to the maximal value of the index for graphs with given numbers of vertices and edges. None of the conjectures has been resolved so far. We present partial results and provide some indications that the conjectures are very hard.

AB - We consider four conjectures related to the largest eigenvalue of (the adjacency matrix of) a graph (i.e., to the index of the graph). Three of them have been formulated after some experiments with the programming system AutoGraphiX, designed for finding extremal graphs with respect to given properties by the use of variable neighborhood search. The conjectures are related to the maximal value of the irregularity and spectral spread in n-vertex graphs, to a Nordhaus-Gaddum type upper bound for the index, and to the maximal value of the index for graphs with given numbers of vertices and edges. None of the conjectures has been resolved so far. We present partial results and provide some indications that the conjectures are very hard.

KW - Adjacency matrix

KW - AutoGraphiX

KW - Conjectures

KW - Extremal graph

KW - Graph

KW - Index

KW - Irregularity

KW - Largest eigenvalue

KW - Spectral spread

KW - Variable neighborhood search

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

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

U2 - 10.1016/j.ejor.2006.12.059

DO - 10.1016/j.ejor.2006.12.059

M3 - Article

AN - SCOPUS:44649178338

SN - 0377-2217

VL - 191

SP - 661

EP - 676

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -

Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this