Hits:

Indexed by:Journal Papers

Date of Publication:2015-10-30

Journal:DISCRETE APPLIED MATHEMATICS

Included Journals:SCIE、EI、Scopus

Volume:194

Page Number:178-182

ISSN No.: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.