Decycling bubble sort graphs

被引：4

作者：

Wang, Jian ^{[1
]}

Xu, Xirong ^{[1
]}

Gao, Liqing ^{[2
]}

Zhang, Sijia ^{[1
]}

Yang, Yuansheng ^{[1
]}

机构：

[1] Dalian Univ Technol, Sch Comp Sci & Technol, Dalian 116024, Peoples R China

[2] Dalian Univ Technol, Sch Management Sci & Engn, Dalian 116024, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2015年 / 194卷

关键词：

Graph theory; Decycling set; Decycling number; Bubble sort graphs; Cycles; Acyclic subgraph; Networks; FEEDBACK VERTEX SET; BOUNDS;

D O I：

10.1016/j.dam.2015.05.024

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：178 / 182

页数：5