MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Orange Mar 28 '11 at 3:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.