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

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 propert...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2008-12, Vol.191 (3), p.661-676
Main Authors: Aouchiche, M., Bell, F.K., Cvetković, D., Hansen, P., Rowlinson, P., Simić, S.K., Stevanović, D.
Format: Article
Language:English
Subjects:
Adjacency matrix
Applied sciences
AutoGraphiX
Computer science
control theory
systems
Conjectures
Eigenvalues
Exact sciences and technology
Extremal graph
Graph
Graph theory
Graphs
Index
Information retrieval. Graph
Irregularity
Largest eigenvalue
Optimization algorithms
Spectral spread
Studies
Theoretical computing
Variable neighborhood search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2006.12.059