2

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?

flag
1 
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 2011 at 3:28

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.