Spectral radii of graphs with given chromatic number

被引：37

作者：

Feng, Lihua ^{[1
]}

Li, Qiao ^{[1
]}

Zhang, Xiao-Dong ^{[1
]}

机构：

[1] Shanghai Jiao Tong Univ, Dept Math, Shanghai 200240, Peoples R China

来源：

APPLIED MATHEMATICS LETTERS | 2007年 / 20卷 / 02期

基金：

中国国家自然科学基金;

关键词：

chromatic number; spectral radius;

D O I：

10.1016/j.aml.2005.11.030

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We consider the set G(n,k) of graphs of order n with the chromatic number k >= 2. In this note, we prove that in G(n,k) the Turan graph T-n,T-k has the maximal spectral radius; and P-n if k = 2, C-n if k = 3 and n is odd, C-n-1(1) if k = 3 and n is even, K-k((l)) if k >= 4 has the minimal spectral radius. Thus we answer a problem raised by Cao [D.S. Cao, Index function of graphs, J. East China Norm. Univ. Sci. Ed. 4 (1987) 1-8 (in Chinese). MR89m:05084] and Hong [Y. Hong, Bounds of eigenvalues of graphs, Discrete Math. 123 (1993) 65-74] in the affirmative. (C) 2006 Elsevier Ltd. All rights reserved.

引用

页码：158 / 162

页数：5

共 11 条

[1]

BOLLOBAS B, 1978, EXTREMAL GRAPH THEOR, pCH5

[2] On colouring the nodes of a network [J].

Brooks, RL .

PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1941, 37 :194-197

[3]

Cao DS, 1998, LINEAR ALGEBRA APPL, V270, P1

[4]

CAO DS, 1987, J E CHINA NORM U SCI, V4, P1

[5]

CVETKOVIC D, 1997, EIGENSPACES GRAPHS

[6]

Cvetkovic D. M., 1980, Spectra of Graphs-Theory and Application

[7] LOWER BOUNDS FOR THE CLIQUE AND THE CHROMATIC-NUMBERS OF A GRAPH [J].

EDWARDS, CS ;

ELPHICK, CH .

DISCRETE APPLIED MATHEMATICS, 1983, 5 (01) :51-64

[8] BOUNDS OF EIGENVALUES OF GRAPHS [J].

HONG, Y .

DISCRETE MATHEMATICS, 1993, 123 (1-3) :65-74

[9]

KRIVELEVICH M, 1998, ELECTRON J COMB, V1, pR4

[10]

Li Qiao, 1979, Acta Mathematicae Applacatae Sinica, V2, P167

← 1 2 →