点击次数：

论文类型：期刊论文

发表时间：2015-10-30

发表刊物：DISCRETE APPLIED MATHEMATICS

收录刊物：SCIE、EI、Scopus

卷号：194

页面范围：178-182

ISSN号：0166-218X

关键字：Graph theory; Decycling set; Decycling number; Bubble sort graphs; Cycles; Acyclic subgraph; Networks

摘要：The decycling number of a graph G is the minimum number of vertices whose removal from G results in an acyclic subgraph. In this paper we show that the decycling number f(n) of the bubble sort graph B-n satisfies these inequalities:
   n!(n - 3)/2(n - 2) + 1 <= f(n) <= n!(2n - 3)/4(n - 1). (C) 2015 Elsevier B.V. All rights reserved.