The smallest eigenvalue of Kr-free graphs

被引：16

作者：

Nikiforov, V ^{[1
]}

机构：

[1] Memphis State Univ, Dept Math Sci, Memphis, TN 38152 USA

来源：

DISCRETE MATHEMATICS | 2006年 / 306卷 / 06期

关键词：

graph eigenvalues; smallest eigenvalue; second eigenvalue; clique number; independence number;

D O I：

10.1016/j.disc.2006.01.014

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a Kr+1-free graph with n vertices and m edges, and let lambda(n)(G) be the smallest eigenvalue of its adjacency matrix. We show that lambda(n)(G) < - 2(r+1)m(r)/rn(2r-1). This implies also that if G is a d-regular graph of order n and independence number r, the second eigenvalue of G satisfies lambda(2)(G) >= -1 + 2/r (n-1-d)(r)/n(r-1). (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：612 / 616

页数：5

共 6 条

[1]

[Anonymous], 1998, GRAD TEXT M, DOI 10.1007/978-1-4612-0619-4_7

[2] Graphs and Hermitian matrices:: eigenvalue interlacing [J].

Bollobás, B ;

Nikiforov, V .

DISCRETE MATHEMATICS, 2004, 289 (1-3) :119-127

[3] QUASI-RANDOM GRAPHS [J].

CHUNG, FRK ;

GRAHAM, RL ;

WILSON, RM .

COMBINATORICA, 1989, 9 (04) :345-362

[4]

Hoffman A. J., 1970, GRAPH THEORY ITS APP, P79, DOI DOI 10.1142/97898127969360041

[5] Triangle factors in sparse pseudo-random graphs [J].

Krivelevich, M ;

Sudakov, B ;

Szabó, T .

COMBINATORICA, 2004, 24 (03) :403-426

[6] Some inequalities for the largest eigenvalue of a graph [J].

Nikiforov, V .

COMBINATORICS PROBABILITY & COMPUTING, 2002, 11 (02) :179-189

← 1 →