# Find the least number of Dragons required

The following graph represents the positions at Castle Dragonstone. Each edge indicates that the positions are within sight of each other. This is not transitive; i.e., you can't see all the way along a row or column; you can see only the adjacent positions.

King Aerion is putting dragons in his castle. He has a condition that every position in the above graph has to be either occupied by a dragon or within the sight of a dragon. Find the smallest number of dragons that he would need in order to meet this condition.

• Is it right to say that the goal is essential to partition the graph in subgraphs with a maximum diameter of 2 in such a way that you have the least amount of subgraphs?
– Ivo
Jan 26, 2017 at 14:57
• What do you mean it won't work?
– Ivo
Jan 26, 2017 at 15:01
• each such a subgraph has a single dragon on it then
– Ivo
Jan 26, 2017 at 15:04
• A 3x3 grid doesn't have diameter 2. it actually has diameter 4. to get from the topleft position to the bottomright requires 4 steps. A position with a dragon on it with all positions in its sight are allways graphs of diameter 2
– Ivo
Jan 26, 2017 at 15:09
• Vertex Cover? :P Jan 27, 2017 at 10:10

The smallest number of dragons needed is:

40

This problem boils down into finding:

The minimum vertex cover of the 13 x 13 grid-graph. Another term for minimum vertex cover is "Dominating Set". The domination number for a 13 x 13 grid graph is 40. Here is an example covering.

See OEIS article for the domination number

• Damn... thought I'd got this one... +1 Jan 27, 2017 at 14:08
• @BrentHackers Your answer was great, except math. :) Jan 27, 2017 at 14:28
• Harsh... I'm Maths-phobic... Jan 27, 2017 at 14:53