Example of a locally finite graph without a uniform degree bound

114 Views Asked by At

We call an infinite graph locally finite if every vertex of it is of finite degree. A locally finite graph is said to have a uniform degree bound if the degree of every vertex of it is bounded by some fixed positive number, say $D$. Clearly the number of self-avoiding paths of length $n$ starting at any vertex of such a graph is at most $D^n$.

Let us say that a locally finite graph satisfies the bounded connective constant property at a given vertex if for any $n$ the number of self-avoiding paths of length $n$ starting at the given vertex of a locally finite graph is at most $D^n$ for some $D>0$.

I am looking for examples of infinite graphs which are locally finite but without a uniform degree bound, such that, if $N_{n,v}$ denotes the number of self-avoiding paths of length $n$ starting at vertex $v$, then for every $v$, $\limsup\limits_{n\to\infty}(N_{n,v})^\frac{1}{n}<\infty$.

Loosely speaking, I am looking for examples of locally finite graphs which satisfy the bounded connective constant property at every vertex (in a slightly generalized way), but don't have a uniform degree bound. Any help will be highly appreciated.

Also, I am specifically looking for graphs which are connected.

1

There are 1 best solutions below

0
On

If you don't require the graph to be connected it's easy, take one star of each positive integer size (For every $v$ there are no self-avoiding paths of large lengths).

If it must be connected just connect the centers of the start, each with the next.

Explicitly the set of vertices is $(i,j)$ with $j\leq i$ and $i\in \mathbb Z^+$, and only take edges $(a,0) \sim (a,i)$ and $(a,0)\sim (a\pm 1,0)$.

Note that in a self avoiding path all vertices except the first or the last one must be the centers of a star. It follows that the number of such paths is at most something like $2(i+n)^2$ where the initial vertex belongs to the $i'th$ star.