Computer Science ›› 2016, Vol. 43 ›› Issue (5): 13-21.doi: 10.11896/j.issn.1002-137X.2016.05.003

Previous Articles     Next Articles

Feedback Numbers of Generalized Kautz Digraphs GK(3,n)

XU Xi-rong, HUANG Ya-zhen, ZHANG Si-jia and DONG Xue-zhi   

  • Online:2018-12-01 Published:2018-12-01

Abstract: A subset of vertices of a graph G is called a feedback vertex set of G,if its removal results is an acyclic subgraph.This paper investigated the feedback vertex set of generalized Kautz digraphs GK(d,n).Let f(d,n) denote the minimum cardinality over all feedback vertex sets of the Generalized Kautz digraph GK(d,n).The upper bound of the feedback numbers of GK(3,n) is obtained as follows f(3,n)≤n+5n8 - 3n4- 4n7+3.

Key words: Topological structure of interconnection network,Feedback vertex set,Feedback number,Generalized Kautz digraphs,Acyclic subgraph

[1] Xu Xi-rong,Wang Bao-cai,Yang Yuan-sheng.Feedback Number of (n,k)-Star Graphs[J].Utilitas Mathematica,2014,95:51-63
[2] Garey M R,Johnson D S.Computers and Intractability [M].Freeman,San Francisco,CA,1979
[3] Kautz W H.Design of optimal interconnection networks formultiprocessors[J].Architecture and Design of Digital Compu-ters,Nato Advanced Summer Institute,1969:249-272
[4] Kralovivc R,Rvuzivcka P.Minimum feedback vertex sets inshuffle-based interconnection networks[J].Information Proces-sing Letters,2003,86:191-196
[5] Xu Jun-ming,Wu Ye-zhou,Huang Jia.Feedback Number ofKautz Digraphs[J].Discrete Math,2007,307(13):1589-1599
[6] Xu Xi-rong,Cao Yong-chang,Xu Jun-ming,et al.FeedbackNumbers of De Bruijn Digraphs[J].Computer and Mathematics with Applications,2010,59:716-723
[7] Xu Xi-rong,Xu Jun-ming,Cao Yong-chang.Bounds on Feedback Numbers of De Bruijn Graphs[J].Taiwanese Journal of Mathematics,2011,15:1101-1113
[8] Xu Xi-rong,Yang Yuan-sheng,Ming Di.Feedback Vertex Set of Generalized De Bruijn Digraphs GB(d,n)[J].Utilitas Math,2009,79:107-124
[9] Xu Xi-rong,Yin Chun,Zhang Si-jia,et al.Improved FeedbackVertex Sets in Kautz Digraphs K(d,n) [C]∥International Conference on Computational Intelligence and Security.Kunming,China,2014,IEEE,2014:161-165
[10] Wang Lei,Xu Xi-rong,Yang Yuan-sheng,et al.Feedback Number of Generalized Kautz Digraphs GK(2,n)[J].Ars Combinatoria,2014,116:147-160

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!