计算机科学 ›› 2016, Vol. 43 ›› Issue (5): 13-21.doi: 10.11896/j.issn.1002-137X.2016.05.003

• 目次 • 上一篇    下一篇

广义Kautz有向图GK(3,n)的反馈数的界

徐喜荣,黄亚真,张思佳,董学智   

  1. 大连理工大学计算机科学与技术学院 大连116024,大连理工大学计算机科学与技术学院 大连116024,大连理工大学计算机科学与技术学院 大连116024,大连理工大学计算机科学与技术学院 大连116024
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金项目(61472465,61170303),辽宁省自然科学基金项目(L2013337)资助

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

摘要: 对于给定的图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。

关键词: 互联网络拓扑结构,反馈点集,反馈数,广义Kautz有向图,无圈子图

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!