Feedback vertex number of Sierpiński-type graphs

Abstract

The feedback vertex number $\tau (G)$ of a graph $G$ is the minimum number of vertices that can be deleted from $G$ such that the resultant graph does not contain a cycle. We show that $\tau (S_p^n)=p^{n-1}(p-2)$ for the Sierpiński graph $S_p^n$ with $p\ge 2$ and $n\ge 1$. The generalized Sierpiński triangle graph $\widehat{S_p^n}$ is obtained by contracting all non-clique edges from the Sierpiński graph $S_p^{n+1}$. We prove that $\tau ({\hat{S}}_3^n)=\frac{3^n+1}{2}=\frac{|V({\hat{S}}_3^n)|}{3}$, and give an upper bound for $\tau ({\hat{S}}_p^n)$ for the case when $p\ge 4$.

20 pages; 8 figures