# 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 Beckers Jan 26 '17 at 14:57
• What do you mean it won't work? – Ivo Beckers Jan 26 '17 at 15:01
• each such a subgraph has a single dragon on it then – Ivo Beckers Jan 26 '17 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 Beckers Jan 26 '17 at 15:09
• Vertex Cover? :P – Laschet Jain Jan 27 '17 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 – Brent Hackers Jan 27 '17 at 14:08
• @BrentHackers Your answer was great, except math. :) – LeppyR64 Jan 27 '17 at 14:28
• Harsh... I'm Maths-phobic... – Brent Hackers Jan 27 '17 at 14:53