Connected graphs of fixed order and size with maximal index: Some spectral bounds

被引：16

作者：

Simic, Slobodan K. ^{[1
]}

Belardo, Francesco ^{[2
]}

Li Marzi, Enzo Maria ^{[2
]}

Tosic, Dejan V. ^{[3
]}

机构：

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

[2] Univ Messina, Dept Math, I-98166 Messina, Italy

[3] Univ Belgrade, Sch Elect Engn, Belgrade 11000, Serbia

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2010年 / 432卷 / 09期

关键词：

Nested split graph; Threshold graph; Adjacency spectrum; Largest eigenvalue; Graph index; Spectral radius; Spectral bounds; RADIUS; EIGENVALUE;

D O I：

10.1016/j.laa.2009.06.043

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The index (or spectral radius) of a simple graph is the largest eigenvalue of its adjacency matrix. For connected graphs of fixed order and size the graphs with maximal index are not yet identified (in the general case). It is known (for a long time) that these graphs are nested split graphs (or threshold graphs). In this paper we use the eigenvector techniques for getting some new (lower and upper) bounds on the index of nested split graphs. Besides we give some computational results in order to compare these bounds. (C) 2009 Elsevier Inc. All rights reserved.

引用

页码：2361 / 2372

页数：12

共 12 条

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

Aouchiche, M. ;

Bell, F. K. ;

Cvetkovic, D. ;

Hansen, P. ;

Rowlinson, P. ;

Simic, S. K. ;

Stevanovic, D. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 191 (03) :661-676

[2]

Brualdi R. A., 1986, Publ. Inst. Math. Belgrade NS, V39, P45

[3] ON THE SPECTRAL-RADIUS OF (0,1)-MATRICES [J].

BRUALDI, RA ;

HOFFMAN, AJ .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1985, 65 (FEB) :133-146

[4]

Cvetkovic D., 1995, Spectra of Graphs Theory and Applications, V3rd

[5]

Cvetkovic D., 1988, Publ. Inst. Math, V44, P29

[6]

Cvetkovic Dragos, 1997, Eigenspaces of Graphs

[7]

Cvetkovic Dragos M., 1990, Linear and Multilinear Algebra, V28, P3, DOI [DOI 10.1080/03081089008818026, 10.1080/03081089008818026, DOI 10.1073/pnas.192407699]

[8] THE MAXIMAL EIGENVALUE OF 0-1 MATRICES WITH PRESCRIBED NUMBER OF ONES [J].

FRIEDLAND, S .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1985, 69 (AUG) :33-69

[9] BOUNDS ON THE SPECTRAL-RADIUS OF GRAPHS WITH E-EDGES [J].

FRIEDLAND, S .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1988, 101 :81-86

[10] ON THE MAXIMAL INDEX OF GRAPHS WITH A PRESCRIBED NUMBER OF EDGES [J].

ROWLINSON, P .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1988, 110 :43-53

← 1 2 →