SOME EIGENVALUE PROPERTIES IN GRAPHS (CONJECTURES OF GRAFFITI .2.)

被引：233
作者：
FAVARON, O
MAHEO, M
SACLE, JF
机构：
[1] L.R.I., Bǎt. 490, Université Paris-Sud
来源：
DISCRETE MATHEMATICS | 1993年 / 111卷 / 1-3期
关键词：
D O I：
10.1016/0012-365X(93)90156-N
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In this paper we improve some classical bounds on the greatest eigenvalue of the adjuacency matrix of a graph. We also give inequalities between the eigenvalues and some other parameters. These results allow us to prove some conjectures of the program Graffiti written by Fajtlowicz. Moreover, the study of the spectrum of graphs obtained by some simple constructions yields infinite families of counterexamples for other conjectures of this program.
引用
收藏
页码：197 / 220
页数：24
相关论文
共 18 条
  • [1] Bondy J.A., 1971, DISCRETE MATH, V1, P121, DOI DOI 10.1016/0012-365X(71)90019-7
  • [2] Cvetkovic D.M., 1988, RECENT RESULTS THEOR
  • [3] Cvetkovic DM., 1979, SPECTRA GRAPHS
  • [4] LOWER BOUNDS FOR THE CLIQUE AND THE CHROMATIC-NUMBERS OF A GRAPH
    EDWARDS, CS
    ELPHICK, CH
    [J]. DISCRETE APPLIED MATHEMATICS, 1983, 5 (01) : 51 - 64
  • [5] Fajtlowicz S., 1987, C NUMER, V60, P187
  • [6] Fajtlowicz S., WRITTEN WALL LIST CO
  • [7] ON THE RESIDUE OF A GRAPH
    FAVARON, O
    MAHEO, M
    SACLE, JF
    [J]. JOURNAL OF GRAPH THEORY, 1991, 15 (01) : 39 - 64
  • [8] FAVARON O, LRI577 U PAR SUD REP
  • [9] FINCK HJ, 1965, I WISS Z TH ILMENAU, V11, P1
  • [10] HAEMERS W. H., 1980, MATH CENTR TRACT, V121
12