Release Time:2019-03-09  Hits:

Indexed by: Journal Papers

Date of Publication: 2015-10-30

Journal: DISCRETE APPLIED MATHEMATICS

Included Journals: Scopus、EI、SCIE

Volume: 194

Page Number: 178-182

ISSN: 0166-218X

Key Words: Graph theory; Decycling set; Decycling number; Bubble sort graphs; Cycles; Acyclic subgraph; Networks

Abstract: 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.