Maximum number of adjacent cells

Question

I'm tryng to solve the following question:

Making a connected graph in a grid of size n*n, where each cell is a node and every node can only connect to a adjacent node, What is the max number of unfilled cells adjacent to a filled cell you can get $\forall n \in N$?

By example this two grids are valid:

And this is an invalid grid because (3, 4) and (4, 3) are disconnected (Disconnected graph).

By example, in a grid of size 4, the max number is 20 and this is one graph that gets it.

Note that unfilled cells adjacent to a filled cell may be off the grid. The grid only limits the filled cells.

Answer 1

In both the path and merely connected versions of the problem, for $n \in \{1,\dots,10\}$, integer linear programming yields optimal values $4, 8, 13, 20, 28, 37, 49, 60, 73, 90$, respectively. For example, here is an optimal solution for $n=10$:

For the path version, optimal for $n=16$ is $206$, rather than your conjectured value of $208$:

Still working on the connected version for $n=16$, but we know that $206$ is a lower bound.

Answer 2

In an $n \times n$ grid, we can prove an upper bound of $\frac23(n^2+4n+1)$ by constructing the graph whose vertices are the filled cells and the "shaded" cells adjacent to them. In this graph, add an edge from each shaded cell to just one neighboring filled cell, and add edges between adjacent filled cells to connect them.

This graph is connected, so if it has $N$ vertices, it must have at least $N-1$ edges. Let $k$ be the number of leaves (all shaded cells are leaves). All non-leaf cells have degree at most $4$, so the degree sum is at most $k + 4(N-k)$; this must be at least $2(N-1)$. From $k + 4(N-k) \ge 2(N-1)$ we get $k \le \frac23(N+1)$.

The number of leaves is at most $k$, and $N$ is at most $n^2+4n$: the $n^2$ cells of the grid, and the $4n$ cells adjacent to them. This gives us the upper bound of $\frac23(n^2+4n+1)$ that we wanted.

When $n \equiv 1 \pmod 3$, we can get a lower bound of $\frac23 (n^2 + 3n + 2)$ by generalizing the construction below:

XXXXXXXXXX
         X
         X
XXXXXXXXXX
X         
X         
XXXXXXXXXX
         X
         X
XXXXXXXXXX

The lower and upper bounds in this case differ by $\frac23(n-1)$.