Queen Covering Problem

Allow me to be nerdy for a bit. I came across an interesting problem the other day that a friend told me about. I did a little research and it turns out that it goes by the name "Queen Covering Problem." The problem is stated like so: Given an 'n x n' chessboard, what is the minimum number of queens that can be placed on the chessboard so that each square is occupied or being attacked by a queen. There is a varient called the "Independent Queen Covering Problem" where you have the added condition that the queens cannot be attacking each other.

So, being an amateur graph theorist, this kind of problem is right up my alley. A dominating set in a graph, G = (V,E), is a subset D of V such that every vertex of V\D is adjacent to some vertex in D. The dominating number of a graph G is the minimum order of any dominating set. This is often denoted gamma(G). The 'n x n' chessboard can be made a graph by taking the squares as vertices and defining two vertices adjacent if they are on the same horizontal, vertical, or diagonal. So the Queen Covering Problem is just a dominating number problem.

This is similar to another more familiar problem called the "Eight Queen Problem," place eight queens on a chessboard so that no two queens are attacking each other. There is even a wikipedia entry on this one:
http://en.wikipedia.org/wiki/Eight_queens_puzzle
The queen covering problem gets a one sentence mention lower on the page, (or at least, it did when I was writing this). Apparently this problem isn't cool enough to get its own wikipedia entry. And according to Wikipedia, (the fount of all knowledge) the domination number for an 'n x n' board is 5.

I've only played around with this problem a little, the next obvious step is just to write a computer program to find these, which I am going to work on. I'll also look around at some combinatoric and graph theory journals to see what people have come up with. If you're reading this and you have any references for me, I'd be happy to hear them.

My results so far:
For n = 1, 2, 3. gamma = 1.
For n = 4. gamma = 2.
For n = 5, 6. gamma = 3.
For n = 7. gamma = 4.
For n = 8. gamma = 5.