Feedback numbers of Kautz undirected graphs
Xirong Xu, Jian Wang, Jun‐Ming Xu, Yongchang Cao · 2012
The feedback number f(d, n) of the Kautz undirected graph UK(d, n) is the minimum number of vertices whose removal results in an acyclic graph. This paper shows ⌈(dn+1 − dn−1 − 1d(d +1)+1)/(2d − 1) ⌉ ≤ 2 f(d, n) ≤ dn − ( ⌊ d2 4 ⌋ +1)dn−2, which implies that f(2,n) = 2n−1,as obtained by Královič andRuˇzička [Information Processing Letters 86 (4) (2003), 191–196].