Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph |
| |
| Authors: | M Aouchiche FK Bell D Cvetković P Hansen P Rowlinson SK Simić D Stevanović |
| |
| Institution: | 1. GERAD and HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Canada H3T 2A7;2. Mathematics and Statistics Group, Department of Computing Science and Mathematics, University of Stirling, FK9 4LA Stirling, Scotland, UK;3. Faculty of Electrical Engineering, University of Belgrade, P.O. Box 35–54, 11120 Belgrade, Serbia and Montenegro;4. Mathematical Institute SANU, Knez Mihailova 35, 11001 Belgrade, Serbia and Montenegro;5. Faculty of Sciences, University of Niš, Višegradska 33, 18000 Niš, Serbia and Montenegro |
| |
| 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: | Graph Adjacency matrix Largest eigenvalue Index Spectral spread Irregularity Variable neighborhood search Extremal graph Conjectures AutoGraphiX |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
