The decycling number of generalized Petersen graphs

被引:14
作者
Gao, Liqing [1 ]
Xu, Xirong [1 ]
Wang, Jian [1 ]
Zhu, Dejun [1 ]
Yang, Yuansheng [1 ]
机构
[1] Dalian Univ Technol, Sch Comp Sci & Technol, Dalian 116024, Peoples R China
关键词
Graph theory; Decycling set; Decycling number; Generalized Petersen graphs; Cycles; Acyclic subgraph; FEEDBACK VERTEX SETS; BOUNDS;
D O I
10.1016/j.dam.2014.09.005
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A subset F subset of V(G) is called a decycling set if the subgraph G - F is acyclic. The minimum cardinality of a decycling set is called the decycling number of G, which is proposed first by Beineke and Vandell (1997). We use del(P-n,P-k) to denote the decycling number of the generalized Petersen graphs Ploc. This paper proves that [GRAPHICS] , (C) 2014 Elsevier B.V. All rights reserved.
引用
收藏
页码:297 / 300
页数:4
相关论文
共 10 条
  • [1] [Anonymous], 1979, COMPUTERS INTRACTABI
  • [2] [Anonymous], 1972, Complexity of Computer Computations, DOI [10.1007/978-3-540-68279-0-8, DOI 10.1007/978-1-4684-2001-2]
  • [3] A 2-approximation algorithm for the undirected feedback vertex set problem
    Bafna, V
    Berman, P
    Fujito, T
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (03) : 289 - 297
  • [4] Bau S., 2002, AUSTRALAS J COMB, V25, P285
  • [5] Beineke LW, 1997, J GRAPH THEOR, V25, P59
  • [6] MAXIMUM INDUCED TREES IN GRAPHS
    ERDOS, P
    SAKS, M
    SOS, VT
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (01) : 61 - 79
  • [7] Feedback vertex set in hypercubes
    Focardi, R
    Luccio, FL
    Peleg, D
    [J]. INFORMATION PROCESSING LETTERS, 2000, 76 (1-2) : 1 - 5
  • [8] Kheddouci H, 2008, DISCRETE MATH THEOR, V10, P57
  • [9] Feedback vertex sets in star graphs
    Wang, FH
    Wang, YL
    Chang, JM
    [J]. INFORMATION PROCESSING LETTERS, 2004, 89 (04) : 203 - 208
  • [10] On the bounds of feedback numbers of (n, k)-star graphs
    Wang, Jian
    Xu, Xirong
    Zhu, Dejun
    Gao, Liqing
    Xu, Jun-Ming
    [J]. INFORMATION PROCESSING LETTERS, 2012, 112 (12) : 473 - 478