4
$\begingroup$

The problem of finding the domination number of Hamming graph $H(3, 2n)$ ($n$ is an integer) was given as a homework for my discrete math class. I didn't manage to solve the question. But later the solution was given to every students and the answer was $n^2/2$.

And now I have a question if there is any generalization of this problem. What kind of Hamming graphs $H(p, q)$ have exact and known domination number?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Well to state the obvious the domination numbers of H(1,n) the complete graph, and H(2,n) the rook's graph are easy. You've pretty much done H(3,n). Try H(4,n). Wish I could be of more help, I'm mostly commenting to draw attention to the problem since I'm also curious. $\endgroup$
    – Orange
    Commented Mar 28, 2011 at 3:28
  • $\begingroup$ Already for the hypercube $H(p,2)$ determining the domination number remains opens, see this paper $\endgroup$
    – Kolja Knauer
    Commented Nov 2 at 10:17

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .