Feedback vertex number of Sierpi{n}ski-type graphs


Abstract in English

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{n}ski graph $S_p^n$ with $pgeq 2$ and $ngeq 1$. The generalized Sierpi{n}ski triangle graph $hat{S_p^n}$ is obtained by contracting all non-clique edges from the Sierpi{n}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 $pgeq 4$.

Download