THE SLATER AND SUB-k-DOMINATION NUMBER OF A GRAPH WITH APPLICATIONS TO DOMINATION AND k-DOMINATION

被引：1

作者：

Amos, David ^{[1
]}

Asplund, John ^{[2
]}

Brimkov, Boris ^{[3
]}

Davila, Randy ^{[4
]}

机构：

[1] Texas A&M Univ, College Stn, TX 77843 USA

[2] Dalton State Coll, Dalton, GA USA

[3] Rice Univ, Houston, TX 77251 USA

[4] Univ Johannesburg, Johannesburg, South Africa

来源：

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

基金：

美国国家科学基金会;

关键词：

Slater number; domination number; sub-k-domination number; k-domination number; degree sequence index strategy; BOUNDS;

D O I：

10.7151/dmgt.2134

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper we introduce and study a new graph invariant derived from the degree sequence of a graph G, called the sub-k-domination number and denoted subk(G). This invariant serves as a generalization of the Slater number; in particular, we show that subk(G) is a computationally efficient sharp lower bound on the k-domination number of G, and improves on several known lower bounds. We also characterize the sub-k-domination numbers of several families of graphs, provide structural results on sub-k-domination, and explore properties of graphs which are subk(G)-critical with respect to addition and deletion of vertices and edges.

引用

页码：209 / 225

页数：17

共 24 条

[1]

[Anonymous], 2004, THESIS U HOUSTON

[2]

[Anonymous], 2010, C NUMER

[3]

Caro Y., 1990, INT J MATH MATH SCI, V13, P205, DOI [10.1155/S016117129000031X, DOI 10.1155/S016117129000031X, 10.1155S016117129000031X////]

[4]

Caro Y, 2014, AUSTRALAS J COMB, V59, P1