Geodesic
The Slater and Sub-k-Domination Number of a Graph with Applications to Domination and k-Domination
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 209-225.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2020_40_1_a13,
     author = {Amos, David and Asplund, John and Brimkov, Boris and Davila, Randy},
     title = {The {Slater} and {Sub-k-Domination} {Number} of a {Graph} with {Applications} to {Domination} and {k-Domination}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {209--225},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a13/}
}
TY  - JOUR
AU  - Amos, David
AU  - Asplund, John
AU  - Brimkov, Boris
AU  - Davila, Randy
TI  - The Slater and Sub-k-Domination Number of a Graph with Applications to Domination and k-Domination
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 209
EP  - 225
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a13/
LA  - en
ID  - DMGT_2020_40_1_a13
ER  - 
%0 Journal Article
%A Amos, David
%A Asplund, John
%A Brimkov, Boris
%A Davila, Randy
%T The Slater and Sub-k-Domination Number of a Graph with Applications to Domination and k-Domination
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 209-225
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a13/
%G en
%F DMGT_2020_40_1_a13
Amos, David; Asplund, John; Brimkov, Boris; Davila, Randy. The Slater and Sub-k-Domination Number of a Graph with Applications to Domination and k-Domination. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 209-225. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a13/

[1] Y. Caro and R. Pepper, Degree sequence index strategy, Australas. J. Combin. 59 (2014) 1–23.

[2] Y. Caro and Y. Roditty, A note on the k-domination number of a graph, Int. J. Math. Math. Sci. 13 (1990) 205–206. doi:10.1155/S016117129000031X

[3] E. DeLaViña, C.E. Larson, R. Pepper and B. Waller, Graffiti.pc on the 2 -domination number of a graph, Congr. Numer. 203 (2010) 15–32.

[4] W.J. Desormeaux, T.W. Haynes and M.A. Henning, Improved bounds on the domination number of a tree, Discrete Appl. Math. 177 (2014) 88–94. doi:10.1016/j.dam.2014.05.037

[5] M. Dorfling, W.D. Goddard and M.A. Henning, Domination in planar graphs with small diameter II, Ars Combin. 78 (2006) 237–255.

[6] Z. Du and A. Ilić, A proof of the conjecture regarding the sum of domination number and average eccentricity, Discrete Appl. Math. 201 (2016) 105–113. doi:10.1016/j.dam.2015.08.002

[7] O. Favaron, M. Mahěo and J.F. Saclě, On the residue of a graph, J. Graph Theory 15 (1991) 39–64. doi:10.1002/jgt.3190150107

[8] O. Favaron, A. Hansberg and L. Volkmann, On the k-domination and minimum degree in graphs, J. Graph Theory 57 (2008) 33–40. doi:10.1002/jgt.20279

[9] J.F. Fink and M.S. Jacobson, n-domination in graphs, Graph Theory with Applications to Algorithms and Computer Science (Kalamazoo, Mich., 1987) 283–300.

[10] M. Gentner and D. Rautenbach, Some comments on the Slater number, (2016). preprint arXiv:1608.04560v1

[11] R. Glebov, A. Liebenau and T. Szabó, On the concentration of the domination number of the random graph, SIAM J. Discrete Math. 29 (2015) 1186–1206. doi:10.1137/12090054X

[12] A. Hansberg, Bounds on the connected k-domination number in graphs, Discrete Appl. Math. 158 (2010) 1506–1510. doi:10.1016/j.dam.2010.05.021

[13] A. Hansberg and R. Pepper, On k-domination and j-independence in graphs, Discrete Appl. Math. 161 (2013) 1472–1480. doi:10.1016/j.dam.2013.02.008

[14] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Decker, New York, 1998).

[15] T. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Decker, New York, 1998).

[16] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013). doi:10.1007/978-1-4614-6525-6

[17] M.S. Jacobson and K. Peters, Complexity questions for n-domination and related parameters, Congr. Numer. 68 (1989) 7–22.

[18] A.P. Kazemi, On the total k-domination number of graphs, Discuss. Math. Graph Theory 32 (2012) 419–26. doi:10.7151/dmgt.1616

[19] M. Lemańska, Lower bound on the domination number of a tree, Discuss. Math. Graph Theory 24 (2004) 165–169. doi:10.7151/dmgt.1222

[20] R. Pepper, Binding Independence, PhD Thesis (University of Houston 2004).

[21] R. Pepper, Implications of some observations about the k-domination number, Congr. Numer. 206 (2010) 65–71.

[22] D. Rautenbach and L. Volkmar, New bounds on the k-domination number and the k-tuple domination number, Appl. Math. Lett. 20 (2007) 98–102. doi:10.1016/j.aml.2006.03.006

[23] P.J. Slater, Locating dominating sets and locating-dominating sets, in: Graph Theory, Combinatorics, and Applications, Proceedings of the 7th Quadrennial International Conference on the Theory and Applications of Graphs 2 (1995) 1073–1079.

[24] D. Stevanović, M. Aouchiche and P. Hansen, On the spectral radius of graphs with a given domination number, Linear Algebra Appl. 428 (2008) 1854–1864. doi:10.1016/j.laa.2007.10.024