Authors:
D. Amos, J. Asplund, B. Brimkov, R. Davila
Title:
The Slater and sub-k-domination number of a graph with applications to domination and k-domination
Source:
Discussiones Mathematicae Graph Theory
Received 15.02.2017, Revised 05.02.2018, Accepted 28.02.2018, doi: 10.7151/dmgt.2134

Abstract:
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.
Keywords:
Slater number, domination number, sub-k-domination number, k-domination number, degree sequence index strategy

Links:
PDF