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

被引：36

作者：

Aouchiche, M. ^{[2
,3
]}

Bell, F. K. ^{[4
]}

Cvetkovic, D. ^{[1
]}

Hansen, P. ^{[2
,3
]}

Rowlinson, P. ^{[4
]}

Simic, S. K. ^{[5
]}

Stevanovic, D. ^{[6
]}

机构：

[1] Univ Belgrade, Fac Elect Engn, Belgrade 11120, Serbia

[2] GERAD, Montreal, PQ H3T 2A7, Canada

[3] HEC Montreal, Montreal, PQ H3T 2A7, Canada

[4] Univ Stirling, Dept Comp Sci & Math, Math & Stat Grp, Stirling FK9 4LA, Scotland

[5] SANU, Inst Math, Belgrade 11001, Serbia

[6] Univ Nis, Fac Sci, Nish 18000, Serbia

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2008年 / 191卷 / 03期

关键词：

graph; adjacency matrix; largest eigenvalue; index; spectral spread; irregularity; variable neighborhood search; extremal graph; conjectures; AutoGraphiX;

D O I：

10.1016/j.ejor.2006.12.059

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：661 / 676

页数：16

共 49 条

[31] Variable neighborhood search for extremal graphs.: 10.: Comparison of irregularity indices for chemical trees [J].

Gutman, I ;

Hansen, P ;

Mélot, H .

JOURNAL OF CHEMICAL INFORMATION AND MODELING, 2005, 45 (02) :222-230

[32]

Hansen P, 2005, DIMACS SER DISCRET M, V69, P253

[33]

Hansen P, 2005, MATCH-COMMUN MATH CO, V54, P221

[34] Variable Neighborhood search for extremal graphs.: 6.: Analyzing bounds for the connectivity index [J].

Hansen, P ;

Mélot, H .

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 2003, 43 (01) :1-14

[35] Variable neighborhood search: Principles and applications [J].

Hansen, P ;

Mladenovic, N .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2001, 130 (03) :449-467

[36]

HANSEN P, 2005, ELECT NOTES DISCRETE, V19, P111

[37]

HONG Y, 1988, LINEAR ALGEBRA APPL, V108, P135

[38] A sharp upper bound of the spectral radius of graphs [J].

Hong, Y ;

Shu, JL ;

Fang, KF .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 81 (02) :177-183

[39]

Lovasz L., 1973, Period. Math. Hung., V3, P175, DOI DOI 10.1007/BF02018473

[40] Variable neighborhood search [J].

Mladenovic, N ;

Hansen, P .

COMPUTERS & OPERATIONS RESEARCH, 1997, 24 (11) :1097-1100

← 1 2 3 4 5 →