On feedback number of locally twisted cube
Zhang Si-ji · 2014
The minimum feedback point set problem is known to be NP-hard for general network(graphs).As an important interconnection network topological structure,the n-dimensional locally twisted cube network Qltnis a new variant of n-dimensional hypercube network Qn,which possesses some properties superior to those of Qn.Since the last bytes in vertex set of Qltnare different,vertex set of Qltnis divided into two disjoint subsets.By constructing a maximal acyclic subgraph of Qltn,the upper limit of feedback number is attained.It is proved that for any positive integer n≥2,there is a constant c∈(0,1),which makes the feedback number of Qltnas follows:f(n)=2n-1(1-c/(n-1)).