SPECTRAL CHARACTERIZATIONS AND EMBEDDINGS OF GRAPHS

被引：40

作者：

DOOB, M ^{[1
]}

CVETKOVIC, D ^{[1
]}

机构：

[1] UNIV BELGRADE, BELGRADE, YUGOSLAVIA

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 1979年 / 27卷 / OCT期

关键词：

D O I：

10.1016/0024-3795(79)90028-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The least eigenvalue of the 0-1 adjacency matrix of a graph is denoted λ G. In this paper all graphs with λ(G) greater than -2 are characterized. Such a graph is a generalized line graph of the form L(T;1,0,...,0), L(T), L(H), where T is a tree and H is unicyclic with an odd cycle, or is one of 573 graphs that arise from the root system E8. If G is regular with λ(G)>-2, then Gis a clique or an odd circuit. These characterizations are used for embedding problems; λR(H) = sup{λ(G)z.sfnc;H in G; G regular}. H is an odd circuit, a path, or a complete graph iff λR(H)> -2. For any other line graph H, λR(H) = -2. A similar result holds for complete multipartite graphs. © 1979.

引用

页码：17 / 26

页数：10

共 12 条

[1]

Beineke LW, 1970, J COMBIN THEORY, V9, P129

[2]

BUSSEMAKER F, 1976, 76WSK05 TU EINDH TH

[3] LINE GRAPHS, ROOT SYSTEMS, AND ELLIPTIC GEOMETRY [J].

CAMERON, PJ ;

GOETHALS, JM ;

SEIDEL, JJ ;

SHULT, EE .

JOURNAL OF ALGEBRA, 1976, 43 (01) :305-327

[4]

Doob M., 1973, Journal of Combinatorial Theory, Series B, V15, P40, DOI 10.1016/0095-8956(73)90030-0

[5]

Doob M., 1974, Journal of Combinatorial Theory, Series B, V17, P244, DOI 10.1016/0095-8956(74)90031-8

[6] GRAPHS WHOSE LEAST EIGENVALUE EXCEEDS-1-SQUARE-ROOT-2 [J].

HOFFMAN, AJ .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1977, 16 (02) :153-165

[7] CHANGE IN LEAST EIGENVALUE OF ADJACENCY MATRIX OF A GRAPH UNDER IMBEDDING [J].

HOFFMAN, AJ .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1969, 17 (04) :664-&

[8]

HOFFMAN AJ, UNPUBLISHED

[9]

HOFFMAN AJ, 1968, BEITRAGE GRAPHENTHEO, P75

[10]

HOFFMAN AJ, 1970, COMBINATORIAL STRUCT, P173

← 1 2 →