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

M. Aouchiche, F.K. Bell, D. Cvetkovic, P. Hansen, P. Rowlinson, S.K. Simic and D. Stevanovic

European Journal of Operational Research, 2008, vol. 191, issue 3, pages 661-676

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.

Downloads: (external link)
http://www.sciencedi ... 8092fafe562a67276a67
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Access Statistics for this article

European Journal of Operational Research is edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Series data maintained by Heidi Boesdal ().