The Hamming graph efficient domination divisibility conjecture

Let q=pbq=p^b for a prime pp, and let H(q,d)H(q,d) denote the Hamming graph with alphabet size qq and dimension dd. An efficient (1,k)(1,k)-dominating function is a function of the type specified in the paper whose domination condition is attained efficiently. Suppose that

(d1)q+1=pam,(d-1)q+1=p^a m,

where mm is not divisible by pp. Hamming graph efficient domination conjecture. The graph H(q,d)H(q,d) has an efficient (1,k)(1,k)-dominating function if and only if 1kleq(q1)d+11\leq kleq (q-1)d+1 and kk is a multiple of mm. This conjecture asserts that the necessary divisibility condition is sufficient for Hamming graphs when qq is a prime power; its resolution is not supplied in the source.

Sources & referencesView supporting material

Primary source

Brendan Rooney, “Efficient (j,k)-Domination in Regular Graphs”, arXiv:2107.09758 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.