Exact feedback vertex number of generalized Sierpiński triangle graphs

Let Spn^\hat{S_p^n} be the generalized Sierpiński triangle graph with integers n3n\geq 3 and p4p\geq 4, and let f(G)f(G) denote the feedback vertex number of a graph GG, namely the minimum number of vertices whose deletion makes GG acyclic. Feedback vertex number conjecture.

f(Spn^)={pnpn18+pn2++p8+5p8,if p is even,pnpn1+pn25p+38,if p is odd.f(\hat{S_p^n})=\left\{\begin{array}{ll}p^n-\frac{p^{n-1}}{8}+\frac{p^{n-2}+\cdots+p}{8}+\frac{5p}{8}, & \text{if }p\text{ is even},\\ p^n-\frac{p^{n-1}+p^{n-2}-5p+3}{8}, & \text{if }p\text{ is odd}. \end{array}\right.

The preceding result gives an upper bound for f(Spn^)f(\hat{S_p^n}) by constructing an induced forest, and the authors suspect that this bound is exact for all n3n\geq 3 and p4p\geq 4.

Sources & referencesView supporting material

Primary source

LiLi Yuan, Baoyindureng Wu and Biao Zhao, “Feedback vertex number of Sierpiński-type graphs”, arXiv:1710.01947 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.