3
$\begingroup$

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. enter image description here

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Yolov4
    Jul 17, 2023 at 3:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – Highheath
    Jul 17, 2023 at 7:27

1 Answer 1

4
$\begingroup$

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.

enter image description here

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|)}$.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Highheath
    Jul 17, 2023 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.