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

共 12 条

[1]

[Anonymous], 1979, COMPUTERS INTRACTABI

[2]

[Anonymous], 2004, INTRO COMBINATORICS

[3] A 2-approximation algorithm for the undirected feedback vertex set problem [J].

Bafna, V ;

Berman, P ;

Fujito, T .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (03) :289-297

[4]

Bau S, 2002, J Australas Combin, V25, P285

[5]

Beineke LW, 1997, J GRAPH THEOR, V25, P59

[6] New bounds on the size of the minimum feedback vertex set in meshes and butterflies [J].

Caragiannis, I ;

Kaklamanis, C ;

Kanellopoulos, P .

INFORMATION PROCESSING LETTERS, 2002, 83 (05) :275-280

[7] MAXIMUM INDUCED TREES IN GRAPHS [J].

ERDOS, P ;

SAKS, M ;

SOS, VT .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (01) :61-79

[8] Feedback vertex set in hypercubes [J].

Focardi, R ;

Luccio, FL ;

Peleg, D .

INFORMATION PROCESSING LETTERS, 2000, 76 (1-2) :1-5

[9]

Karp R.M., 1972, PLENUM PRESS SURV ST, P85, DOI 10.1007/978-1-4684-2001-2_9

[10] Feedback vertex sets in star graphs [J].

Wang, FH ;

Wang, YL ;

Chang, JM .

INFORMATION PROCESSING LETTERS, 2004, 89 (04) :203-208

← 1 2 →