An Extremal Graph Problem on a Grid and an Isoperimetric Problem for Polyominoes

Let G denote the infinite grid graph with vertex set \ (a, b) \: \, a, b Z\ and edge set \ \{u, v\: |u-v|=1 \;or\; |u-v| = 2 \}. A question in landscape ecology, restated in graph theoretic terms, asks the following. What is the maximum number of edges in an induced subgraph of G of order n? It was conjectured by Taliceo and Fleron that the maximum is 4n - 28n-12 \,. We prove the conjecture by formulating and solving a discrete version of the classical isoperimeteric problem.