Decycling Cartesian products of two cycles

被引：33
|
作者：
Pike, DA [1 ]
Zou, YB [1 ]
机构：
[1] Mem Univ Newfoundland, Dept Math & Stat, St John, NF A1C 5S7, Canada
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 2005年 / 19卷 / 03期
关键词：
decycling; cycle; Cartesian product; maximum induced forest;
D O I：
10.1137/S089548010444016X
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The decycling number del(G) of a graph G is the smallest number of vertices which can be removed from G so that the resultant graph contains no cycles. In this paper, we study the decycling number for the family of graphs consisting of the Cartesian product of two cycles. We completely solve the problem of determining the decycling number of C-m square C-n for all m and n. Moreover, we find a vertex set T that yields a maximum induced tree in C-m square C-n.
引用
收藏
页码：651 / 663
页数：13
相关论文
共 50 条
  • [1] Antipodal number of Cartesian products of complete graphs with cycles
    Kumar, Kush
    Panigrahi, Pratima
    COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2025, 10 (01) : 219 - 231
  • [2] Vertex-neighbor-toughness of the Cartesian Products of paths and cycles
    Wei, Zongtian
    Yang, Jingting
    Li, Yinkui
    Yue, Chao
    ARS COMBINATORIA, 2019, 147 : 63 - 78
  • [3] Domination number of Cartesian products of directed cycles
    Zhang, Xindong
    Liu, Juan
    Chen, Xing
    Meng, Jixiang
    INFORMATION PROCESSING LETTERS, 2010, 111 (01) : 36 - 39
  • [4] Italian domination of Cartesian products of directed cycles
    van Bommel, Christopher M.
    DISCRETE APPLIED MATHEMATICS, 2021, 299 : 82 - 86
  • [5] On the Crossing Numbers of Cartesian Products of Small Graphs with Paths, Cycles and Stars
    Clancy K.
    Haythorpe M.
    Newcombe A.
    Journal of Combinatorial Mathematics and Combinatorial Computing, 2024, 119 : 323 - 333
  • [6] Classification of l(2, 1)-labeling of cartesian products of paths and cycles
    Zhao T.
    Zhou X.
    Zhao, Taiyin, 1600, American Scientific Publishers (13): : 388 - 393
  • [7] On L(2,1)-labelings of Cartesian products of paths and cycles
    Kuo, D
    Yan, JH
    DISCRETE MATHEMATICS, 2004, 283 (1-3) : 137 - 144
  • [8] On L(d, 1)-Labelings of the Cartesian Product of Two Cycles
    Lin, Chun-Chun
    Yan, Jing-Ho
    ARS COMBINATORIA, 2015, 122 : 33 - 53
  • [9] Dominator Colorings of Certain Cartesian Products of Paths and Cycles
    Chen, Qin
    Zhao, Chengye
    Zhao, Min
    GRAPHS AND COMBINATORICS, 2017, 33 (01) : 73 - 83
  • [10] Dominator Colorings of Certain Cartesian Products of Paths and Cycles
    Qin Chen
    Chengye Zhao
    Min Zhao
    Graphs and Combinatorics, 2017, 33 : 73 - 83
12345