# Number of "one neighbourhood" search trees in a graph

Consider the following algorithm: We are given a planar graph $$G$$. We initialise a set of vertices $$S$$ to an empty set. We randomly pick a vertex $$v$$ in $$G$$ and insert it in $$S$$. Now we keep including in $$S$$ vertices from the neighbourhood of $$S$$ such that the vertex we include is adjacent to exactly one vertex in $$S$$. We stop expanding $$S$$ when there is no vertex in the neighbourhood of $$S$$ which is adjacent to exactly one vertex in $$S$$. Just like BFS produces a breath first tree and DFS produces a depth first tree, the "one neighbourhood" search above also produces a tree. Give a tight upper bound on the number of such trees in $$G$$.

I expect the number of such trees to be asymptotically lower than O($$2^n$$), where $$n$$ is the number of vertices in $$G$$.

The illustration below shows such a tree in a graph. • Unfortunately, I do not have any reference for it. It turns out that the analysis of one of the algorithms I am working on boils down to this problem. Jul 17 at 3:21
• I don't have an answer, but it's clear that this procedure yields exactly the set of maximal induced trees in $G$ (for any $G$, not just planar ones). So there may be someone who have looked into that before. Jul 17 at 7:27

Consider the following planar graph $$G$$. There are $$n+2$$ vertices: $$\{x,y,u_1,\dotsc,u_n,v_1,\dotsc,v_n\}$$. The edge set is $$\{(x,y),(x,u_1),\dotsc,(x,u_n),(y,v_1),\dotsc,(y,v_n),(u_1,v_1),\dotsc,(u_n,v_n)\}$$.
Suppose your algorithm initially picks $$x$$ and $$y$$ in $$S$$. Then, the algorithm can construct $$2^n$$ possible search trees depending on whether $$u_i$$ or $$v_i$$ is included in the serach tree for each $$i \in \{1,\dotsc,n\}$$. Therefore, there are $$2^{\Omega(|V|)}$$ possible search trees for this graph. Note that this is asymptotically tight bound in the exponent since in a planar graph, the number of edges are linearly bounded by the number of vertices, i.e., $$|E| = O(|V|)$$ (see here for the properties of a planar graph). Therefore, the number of subgraphs of any planar graph are at most $$2^{O(|V|)}$$.
• Great example, the bound is even tighter than you mentioned since $2^{n-2} = \Omega(2^n)$. Therefore $O(2^n)$ is a tight bound. Jul 17 at 21:53