Efficient (j,k)-Domination in Regular Graphs

arXiv2107.09758MaRDI QIDQ6373341FDOQ6373341

Authors: Brendan Rooney 

Publication date: 20 July 2021

Abstract: Rubalcaba and Slater (Robert R. Rubalcaba and Peter J. Slater. Efficient (j,k)-domination. Discuss. Math. Graph Theory, 27(3):409-423, 2007.) define a $(j,k)$-dominating function on graph $X$ as a function $f:V(X)ightarrow0,ldots,j$ so that for each $vinV(X)$, $f(N[v])geqk$, where $N[v]$ is the closed neighbourhood of $v$. Such a function is efficient if all of the vertex inequalities are met with equality. They give a simple necessary condition for efficient domination, namely: if $X$ is an $r$-regular graph on $n$ vertices that has an efficient $(1,k)$-dominating function, then the size of the corresponding dominating set divides $ncdotk$. The Hamming graph $H(q,d)$ is the graph on the vectors $mathbb{Z}_q^d$ where two vectors are adjacent if and only if they are at Hamming distance $1$. We show that if $q$ is prime, then the previous necessary condition is sufficient for $H(q,d)$ to have an efficient $(1,k)$-dominating function. This result extends a result of Lee (Jaeun Lee. Independent perfect domination sets in Cayley graphs. J. Graph Theory, 37(4):213-219, 2001.) on independent perfect domination in Cayley graphs. We mention difficulties that arise for $H(q,d)$ when $q$ is a prime power but not prime.

This page was built for publication: Efficient (j,k)-Domination in Regular Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6373341)