1
$\begingroup$

An induced subgraph $G’$ of a graph $G$ is a subset of its vertices along with all the edges that are present in $G$ among those vertices. For $G’$ to be a tree, all vertices of a cycle in $G$ cannot be in $G’$. The tree composed of bold edges in the illustration given below shows an induced tree $T$. Vertex $u$ cannot be included in $T$ because u brings with itself edges $(u, v)$ and $(u, w)$ which completes a cycle $u-v-w-u$ and $T$ no longer remains a tree. $T$ is also a maximal induced tree because no more vertices can be included in $T$ without violating it being a tree.

The question is, what is a tight upper bound on the number of maximal induced trees in a connected triangulated planar graph.

enter image description here

$\endgroup$
1
  • $\begingroup$ This is similar to a question I have posted earlier. link $\endgroup$
    – Yolov4
    Commented Oct 2, 2023 at 14:45

1 Answer 1

2
$\begingroup$

Consider the following planar triangulated 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),(u_1,u_2),\dotsc,(u_{n-1},u_n),(v_1,v_2),\dotsc,(v_{n-1},v_n), (y,u_1),(v_1,u_2),\dotsc,(v_{n-1},u_n)\}$.

Suppose your algorithm initially picks $x$ and $y$ in $S$. Thereafter, suppose the algorithm picks the even numbered vertices $u_{2i}$ and $v_{2i}$ for $i \in \{1,\dotsc,\lfloor n/2 \rfloor\}$. Then, the algorithm can construct $2^{\lfloor n/2 \rfloor}$ possible induced trees depending on whether $u_{2i}$ or $v_{2i}$ is included in the induced tree for each $i \in \{1,\dotsc,\lfloor n/2 \rfloor\}$. Therefore, there are $2^{\Omega(|V|)}$ possible induced 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
  • $\begingroup$ I was also wondering about what is the bound on number of such trees in a 3-regular planar graph. $\endgroup$
    – Yolov4
    Commented Oct 29, 2023 at 14:24

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.