|
个人信息Personal Information
副教授
博士生导师
硕士生导师
性别：女
毕业院校：大连理工大学
学位：博士
所在单位：计算机科学与技术学院
学科：计算机软件与理论
联系方式：0411-84706009-3913
电子邮箱：xirongxu@dlut.edu.cn
BOUNDS ON FEEDBACK NUMBERS OF DE BRUIJN GRAPHS
点击次数：
论文类型：期刊论文
发表时间：2011-06-01
发表刊物：TAIWANESE JOURNAL OF MATHEMATICS
收录刊物：Scopus、SCIE
卷号：15
期号：3
页面范围：1101-1113
ISSN号：1027-5487
关键字：Graph theory; Feedback vertex set; Feedback number; de Bruijn graphs; Cycles; Scyclic subgraph; Networks
摘要：The feedback number of a graph G is the minimum number of vertices whose removal from G results in an acyclic subgraph. We use f(d, n) to denote the feedback number of the de Bruijn graph UB(d, n). R. Kralovic and P. Ruzicka [Minimum feedback vertex sets in shuffle-based interconnection networks. Information Processing Letters, 86 (4) (2003), 191-196] proved that f (2, n) = [2(n)-2/3]. This paper gives the upper bound on f(d, n) for d >= 3, that is, f (d, n) <= d(n) (1 - (d/1+d)(d-1)) + ((n+d-2)(d-2)).