SOME OBSERVATIONS ON THE SMALLEST ADJACENCY EIGENVALUE OF A GRAPH

被引：9

作者：

Cioaba, Sebastian M. ^{[1
]}

Elzinga, Randall J. ^{[2
]}

Gregory, David A. ^{[3
]}

机构：

[1] Univ Delaware, Dept Math Sci, Newark, DE 19716 USA

[2] Akira Hlth, Toronto, ON, Canada

[3] Queens Univ Kingston, Dept Math, Kingston, ON, Canada

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2020年 / 40卷 / 02期

基金：

加拿大自然科学与工程研究理事会;

关键词：

graph spectrum; smallest eigenvalue; adjacency matrix; graph decomposition; clique partition; claw-free graphs; maximum cut; LEAST EIGENVALUE; SPECTRAL-RADIUS; REGULAR GRAPHS; RANDOM-WALKS; MAX CUT; SUBGRAPHS;

D O I：

10.7151/dmgt.2285

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we discuss various connections between the smallest eigen-value of the adjacency matrix of a graph and its structure. There are several techniques for obtaining upper bounds on the smallest eigenvalue, and some of them are based on Rayleigh quotients, Cauchy interlacing using induced subgraphs, and Haemers interlacing with vertex partitions and quotient matrices. In this paper, we are interested in obtaining lower bounds for the smallest eigenvalue. Motivated by results on line graphs and generalized line graphs, we show how graph decompositions can be used to obtain such lower bounds.

引用

页码：467 / 493

页数：27

共 36 条

[1] Eigenvalues of K1,k-Free Graphs and the Connectivity of Their Independence Complexes [J].

Aharoni, Ron ;

Alon, Noga ;

Berger, Eli .

JOURNAL OF GRAPH THEORY, 2016, 83 (04) :384-391

[2] Bipartite subgraphs and the smallest eigenvalue [J].

Alon, N ;

Sudakov, B .

COMBINATORICS PROBABILITY & COMPUTING, 2000, 9 (01) :1-12

[3] LAMBDA-1, ISOPERIMETRIC-INEQUALITIES FOR GRAPHS, AND SUPERCONCENTRATORS [J].

ALON, N ;

MILMAN, VD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (01) :73-88

[4] EIGENVALUES AND EXPANDERS [J].

ALON, N .

COMBINATORICA, 1986, 6 (02) :83-96

[5] Non-backtracking random walks mix faster [J].

Alon, Noga ;

Benjamini, Itai ;

Lubetzky, Eyal ;

Sodin, Sasha .

COMMUNICATIONS IN CONTEMPORARY MATHEMATICS, 2007, 9 (04) :585-603

[6]

[Anonymous], THESIS

[7]

[Anonymous], CAMBRIDGE

[8]

[Anonymous], COMMUNICATION

[9]

[Anonymous], COURSE COMBINATORICS

[10]

[Anonymous], 2001, Algebraic Graph Theory

← 1 2 3 4 →