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


  • Lili Yuan
  • Baoyindureng Wu
  • Biao Zhao



Sierpi\'{n}ski triangle, Sierpi\'{n}ski graphs, Sierpi\'{n}ski-like graphs, Feedback vertex number


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 $p\geq 2$ and $n\geq 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 $p\geq 4$.


[1] S. Bau, L.W. Beineke, The decycling number of graphs, Australas. J. Comb. 25 (2002) 285-298.

[2] J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer, 2008.

[3] M. Borowiecki, E. Drgas-Burchardt, E. Sidorowicz, A feedback vertex set of 2-degenerate graphs, Theoret. Comput. Sci. 557 (2014) 50-58.

[4] F. Dross, M. Montassier, A. Pinlou, A lower bound on the order of the largest induced forest in planar with high girth, Discrete Appl. Math. 214 (2016) 99-107.

[5] P. Erd\H{o}s, M. Saks, V.T. Sos, Maximum induced trees in graphs, J. Comb. Theory, Ser. B 41 (1986) 61-79.

[6] R. Focardi, F.L. Luccio, D. Peleg, Feedback vertex set in hypercubes, Inf. Process. Lett. 76 (2000) 1-5.

[7] S. Gravier, S. Klavzar and M. Mollard, Codes and L(2; 1)-labelings in Sierpinski-like
graphs, Taiwan. J. Math. 9 (2005) 671-681.

[8] M. Hinz, C. Holz auf der Heide, An efficient algorithm to determine all shortest
paths in Sierpinski graphs, Discrete Appl. Math., 177 (2014) 111-120.

[9] A.M. Hinz, D. Parisse, On the planarity of Hanoi graphs, Expo. Math. 20 (2002) 263-268.

[10] A.M. Hinz, D. Parisse, Coloring Hanoi and Sierpiński graphs, Discrete Math. 312 (2012) 1521-1535.

[11] A.M. Hinz, D. Parisse, The average eccentricity of Sierpiński graphs, Graphs Combin. 28 (2012) 671-686.

[12] A.M. Hinz, A. Schief, The average distance on the Sierpiński gasket, Probab. Theory Related Fields 87 (1990) 129-138.

[13] A.M. Hinz, S. Klav\v{z}ar, S.S. Zemlji\v{c}, A survey and classification of Sierpiński-type graphs, Discrete Appl. Math. 217 (2017) 565-600.

[14] K. Hosono, Induced forests in trees and outerplanar graphs, Proc. Fac. Sci. Tokai Univ. 25 (1990) 27-29.

[15] M. Jakovac, A 2-parameter generalization of Sierpi\'{n}ski gasket graphs, Ars Combin. 116 (2014) 395-405.

[16] M. Jakovac and S. Klav\v{z}ar, Vertex-, edge-, and total-coloring of Sierpinski-like graphs,
Discrete Math. 309 (2009) 1548-1556.

[17] Y. Lin, J. Juan, Y. Wang, Finding the edge ranking number through vertex partitions, Discrete Appl. Math. 161 (2013) 1067-1071.

[18] C. Lin, J. Liu, Y. Wang, Global strong defensive alliances of Sierpiński-like graphs, Theory Comput. Syst. 53 (2013) 365-385.

[19] C. Lin, J. Liu, Y. Wang, W. Yen, The hub number of Sierpiński-like graphs, Theory Comput. Syst. 49 (2011) 588-600.

[20] R.M. Karp, R.E. Miller, J.W. Thatcher, Reducibility among combinatorial problems, J. Symb. Log. 40 (1975) 618-619.

[21] T. Kelly, C. Liu,
Minimum size of feedback vertex sets of planar graphs of girth at least five,
European J. Combin. 61 (2017) 138-150.

[22] S. Klavzar, Coloring Sierpinski graphs and Sierpi\'{n}ski gasket graphs, Taiwanese J. Math. 12 (2008) 513-522.

[23] S. Klavzar and U. Milutinovic, Graphs S^n_k and a variant of the tower of Hanoi problem,
Czechoslovak Math. J. 47(122) (1997) 95-104.

[24] S. Klavzar, I. Peterin and S.S. Zemljic, Hamming dimension of a graph- The case of
Sierpi\'{n}ski graphs, Eur. J. combin. 34 (2013) 460-473.

[25] S. Klavzar and S. S. Zemljic, On distances in Sierpinski graphs: almost-extreme vertices
and metric dimension, Appl. Anal. Discrete Math. 7 (2013) 72-82.

[26] S. Klavzar, B. Mohar, Crossing numbers of Sierpi\nski-like graphs, J. Graph Theory 50 (2005) 186-198.

[27] F.R. Madelaine, I.A. Stewart, Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies, Discrete Math. 308 (2008) 4144-4164.

[28] M.J. Pelsmajer, Maximum induced linear forests in outerplanar graphs, Graphs Combin. (2004) 121-129.

[29] D.A. Pike, Decycling hypercubes, Graphs Combin. 19 (2003) 547-550.

[30] D. Parisse, On some metric properties of the Sierpinski graphs $S^n_k$, Ars combin. 90 (2009) 145-160.

[31] M.R. Salavatipour, Large induced forests in triangle-free planar graphs, Graphs Combin. 22 (2006) 113-126.

[32] E. Teufl, S. Wagner, Enumeration of matchings in families of self-similar graphs, Discrete Appl. Math. 158 (2010) 1524-1535.

[33] E. Teufl, S. Wagner, Resistance scaling and the number of spannning trees in self-similar lattices, J. Stat. Phys. 142 (2011) 879-897.

[34] X. Xu, Y. Cao, J.-M. Xu, Y. Wu, Feedback numbers of de Bruijn di-graphs, Comput. Math. Appl. 59 (2010) 716-723.

[35] X. Xu, J.-M. Xu, Y. Cao, Bounds on feedback numbers of de Bruijn graphs, Taiwan. J. Math. 15(3) (2011) 1101-1113.

[36] B. Xue, L. Zuo, G. Li, The hamiltonicity and path t-coloring of Sierpinski-like graphs, Discrete Appl. Math. 160 (2012) 1822-1836.

[37] B. Xue, L. Zuo, G. Wang and G. Li, The linear $t$-coloring of Sierpinski-like graphs,
Graphs Combin., 30 (2014) 755-767.

[38] B. Xue, L. Zuo, G. Wang, G. Li, Shortest paths in Sierpinski graphs, Discrete Appl. Math. 162 (2014) 314-321.