计算机科学 ›› 2016, Vol. 43 ›› Issue (5): 13-21.doi: 10.11896/j.issn.1002-137X.2016.05.003
徐喜荣,黄亚真,张思佳,董学智
XU Xi-rong, HUANG Ya-zhen, ZHANG Si-jia and DONG Xue-zhi
摘要: 对于给定的图G的顶点集的子集F,如果删除F使得剩余子图是无圈子图,则称子集F为图G的反馈点集。研究了广义Kautz有向图GK(d,n)的反馈点集。令f(d,n)表示广义Kautz有向图GK(d,n)的所有反馈集合中顶点个数最少的集合的个数(即广义Kautz有向图GK(d,n)的反馈数),给出了GK(3,n)的反馈数的上界,即 f(3,n)≤n+5n8 - 3n4- 4n7+3。
[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! |
|