Can you randomly sample graphs with quadratic growth? Let $\mathcal{G}$ be the set of all infinite connected graphs with the following properties:


*

*Every vertex has $4$ neighbors

*For every vertex, there are $8$ vertices that have distance exactly $2$ from it.

*For every vertex, there are $12$ vertices that have distance exactly $3$ from it.

*...

*For every vertex, there are $4n$ vertices that have distance exactly $n$ from it.

*...


In other words, the size of any ball of radius $r$ is required to be $r^2+(r+1)^2$. As an example, the infinite square grid is an element of $\mathcal{G}$.
Let $\mathcal{G}_r$ be the set of radius $r$ balls that occur as subgraphs of graphs in $\mathcal{G}$.
Is there a nice (efficient) way to randomly produce graphs in $\mathcal{G}_r$, such that every graph in $\mathcal{G}_r$ has a nonzero chance of being produced?
 A: As (up to isomorphism, and changing font) $G_0$ has 1 member and $G_1$ has 4, I leave it to the poster how to implement random selections from these classes.  That should be straightforward.
I am about to turn enumerating $G_2$ over to a computer, after spending hours trying it by hand.
My chief challenge in attempting the enumeration was to wire up the 8 distance two neighbors to each other in a way that the results could be extended to a member of $G_3$.
If I ignore that I have (not an exact number) on the order of 50 nonisomorphic candidates each of which could produce potentially thousands (more specifically, O(28 choose 6)) of members of $G_2$.
Something that may work efficiently by computer for which I have trouble attempting by hand is stitching: there are 4 nonisomorphic members of $G_1$, and you can try stitching such members together in all possible ways to form larger subgraphs of members of $G_2$ or $G_3$.  Be sure to check that you don't put in too many distance k neighbors when doing so.
If it turns out that stitching yields a small number (less than a thousand) of members of $G_2$, then it may be computationally feasible to enumerate $G_3$.  Until I see an enumeration of $G_2$, any further guesses I make on this are essentially wild speculation.
Gerhard "Real Hand-stitching Is Even Harder" Paseman, 2011.12.02
A: Here is an alternate suggestion which should yield a reasonable upper bound on the size of $G_2$, and may provide the basis of an estimate for the size of $G_3$.
Any member of $G_2$ will be contained in the following class $C$ of graphs on 13 vertices: 5 vertices, which I call the core, will form one of the subgraphs listed in $G_1$, with 8, 10, or 12 edges going from the same 4 vertices of the core to the 8 vertices I call the rim, with an additional 0 up to 6 edges between the vertices of the rim, with every vertex having degree at most 4, and every vertex in the rim being adjacent to at least one of the 4 outer vertices of the core.
It is mildly tedious but not hard to list up to isomorphism those members of $C$ with 0 edges in the rim; there are less than 50 such representatives, which I shall group into a subclass called $C0$.  Now let $i$ be an integer in the range from 0 to 5 and suppose we have the class $Ci$ of graphs which contain all isomorphism types (possibly with some duplication) of members of $C$ which have $i$ edges in the rim.  Add a single edge in all possible ways to each member of $Ci$ and determine which such graphs are isomorphic, and this will form the class $Cj$, where $j=i+1$.  Some candidates made this way will have to be rejected if,  e.g., a vertex gets degree 4 or more.
I suspect that $C1$ will have fewer than 100 members, and that each subclass will have less than 10 times as many members as the previous subclass, except for $C5$ and $C6$, because of the symmetries involved.  There will also be conditions to check on the small neighborhoods of each vertex, and there will be interesting restrictions when passing to $G_3$ which may exclude some members of $C$ from being in $G_2$.
I will attempt an exact enumeration of $C0$, $C1$, and $C2$ by hand.  I make this post because I am not ready to write or borrow a graph isomorphism subroutine to implement in my current computing environment.  This task of enumerating the $Ci$ by computer should be pie for anyone proficient in graph enumeration.  Even having good estimates for $C3$ and $C4$ will be of use, should someone wish to take on a limited version of the task.
Gerhard "Ask Me About System Design" Paseman, 2012.01.11 
