Domination number and Laplacian eigenvalue distribution

被引：21

作者：

Hedetniemi, Stephen T. ^{[1
]}

Jacobs, David P. ^{[1
]}

Trevisan, Vilmar ^{[2
]}

机构：

[1] Clemson Univ, Sch Comp, Clemson, SC 29634 USA

[2] Univ Fed Rio Grande do Sul, Inst Matemat, BR-91509900 Porto Alegre, RS, Brazil

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2016年 / 53卷

关键词：

GRAPHS; TREES;

D O I：

10.1016/j.ejc.2015.11.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let m(G)(I) denote the number of Laplacian eigenvalues of a graph G in an interval I. Our main result is that for graphs having domination number gamma, m(G)[0, 1) <= gamma, improving existing bounds in the literature. For many graphs, m(G)[0, 1) = gamma, or m(G)[0, 1) = gamma-1. (C) 2015 Elsevier Ltd. All rights reserved.

引用

页码：66 / 71

页数：6

共 26 条

[1]

[Anonymous], 1962, MATH SOC C PUBLICATI

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[3]

[Anonymous], 1991, GRAPH THEORY COMBINA

[4] A sharp upper bound on algebraic connectivity using domination number [J].