On independent $k$-domination number of Hamming graphs

Articles in Press

Document Type : Original paper

Author

Department of Mathematical Sciences, Sharif University of Technology, P. O. Box 11155-9415, Tehran, Iran

Abstract

A subset \( S \) of the vertices of a graph is called a \( k \)-dominating set if every vertex outside \( S \) has at least \( k \) neighbors in \( S \). If a \( k \)-dominating set is an independent subset of the vertices, then the set is called an independent \( k \)-dominating set. The size of the smallest such set is called the independent \( k \)-domination number of the graph. In this paper, we derive a lower bound on the independent \( k \)-domination number of Hamming graphs. For some sets of parameters, we show that this lower bound is exact.

Keywords

Main Subjects

References

[1] A. Blokhuis, S. Egner, H.D.L. Hollmann, and J.H. van Lint, On codes with covering radius 1 and minimum distance 2, Indag. Math. 12 (2001), no. 4, 449–452.  https://doi.org/10.1016/S0019-3577(01)80033-1
[2] F. Harary and M. Livingston, Independent domination in hypercubes, Appl. Math. Lett. 6 (1993), no. 3, 27–28. https://doi.org/10.1016/0893-9659(93)90027-K
[3] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core Concepts, Springer International Publishing, 2023.
[4] Z.L. Nagy, On the number of k-dominating independent sets, J. Graph Theory 84 (2017), no. 4, 566–580. https://doi.org/10.1002/jgt.22042
[5] A. Włoch, On 2-dominating kernels in graphs, Australas. J. Combin. 53 (2012), 273–284.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 18 May 2025

Files

Share

How to cite

Statistics