1
$\begingroup$

Defintitions: A graph is said to be r-regular if every of its vertex has a degree $r$. A graph is planar if it can be drawn in a plane without any of its edges intersecting each other except at their endpoints. A graph is connected if there exists at least one path between every pair of its vertices. A tree is connected acyclic graph and a forest is a disconnected acyclic graph. A graph G' is an induced subgraph of a graph G if it inherits all edges over a particular vertex subset of G. A decycling set in a graph is a subset of its vertices, deletion of which induces a forest.

Question: Let $S_n$ be the set of all possible 3-regular connected planar graphs on $n$ vertices. Let N(g) be the number of decycling sets which induce a tree(not a forest) in graph $g$. Let $N_n^*$ = $max\{N(g)\ \forall g\in S_n\}$. Give the smallest order function $f(n)$ such that $N_n^* = O(f(n))$. In other words, give a tight upper bound in terms of n, on the number of tree inducing decycling sets in a 3-regular connected planar graph.

A very loose upper bound of course is $2^n$, which is the number of subsets of vertices. However, not all subsets are trees. And not all trees are induced trees. Moreover, 3-regular graphs are much sparser than a complete graph, and connected planar 3-regular graphs is an even smaller subset of 3-regular graphs. Many applications require the enumeration of certain set of objects associated with a graph, such as the number of spanning trees, or the number of cycles(sometimes special cycles such as cycle basis) or the number of cliques etc. It is natural to wonder if the tight upper bound on the number of objects such as induced trees, and that too in a quite restricted class of graphs i.e. 3-regular connected planar graphs is sub-exponential or even polynomial ?

Illustration: The illustration below shows such a tree in a 3-regular planar graph. The vertices that are not part of the tree compose the decycling set.

enter image description here

$\endgroup$
1
  • $\begingroup$ Please edit your question to clarify what kind of answer you are looking for. Are you looking for an algorithm that takes a graph as input and outputs the number of decycling sets? Do you want a formula as a function of some parameters, like the number of vertices in the graph, over all possible graphs of that size? If so, what parameters do you care about, and what do you mean by "tight"? Surely the upper bound is attained by a complete graph, right? What is the best upper bound you know so far? $\endgroup$
    – D.W.
    Nov 1, 2023 at 5:40

1 Answer 1

1
$\begingroup$

The tight bound on the number of decycling sets is $2^{\Theta(|V|)}$. Consider the following $3$-regular planar graph.

enter image description here

In the decycling set, for each $i \in \{1,\dotsc,n\}$ choose either $a_i$ or $b_i$. Moreover, choose the vertex $c_n$ in the decycling set. Note that removing these vertices induces a tree on the remaining vertices. Thus, there are $2^{n} = 2^{\Omega(|V|)}$ choices for a decycling set. The upper bound is naturally $2^{O(|V|)}$ for any input graph (as you mentioned in the question as well). Thus, the tight bound is $2^{\Theta(|V|)}$.

$\endgroup$

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.