Authors: Aouchiche, Mustapha
Bell, Francis
Cvetković, Dragoš
Hansen, Pierre
Rowlinson, Peter
Simić, Slobodan 
Stevanović, Dragan 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph
Journal: European Journal of Operational Research
Volume: 191
Issue: 3
First page: 661
Last page: 676
Issue Date: 16-Dec-2008
Rank: M21
ISSN: 0377-2217
DOI: 10.1016/j.ejor.2006.12.059
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
Publisher: Elsevier

Show full item record


checked on Jun 23, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.