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 条
  • [21] The secure domination number of Cartesian products of small graphs with paths and cycles
    Haythorpe, Michael
    Newcombe, Alex
    DISCRETE APPLIED MATHEMATICS, 2022, 309 : 32 - 45
  • [22] Hamiltonicity of the cartesian product of two directed cycles minus a subgroup
    Barone, Victoria
    Mauntel, Matthew
    Miller, Micah
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2006, 3 (01) : 39 - 43
  • [23] A note on the chromatic number of the square of the Cartesian product of two cycles
    Shao, Zehui
    Vesel, Aleksander
    DISCRETE MATHEMATICS, 2013, 313 (09) : 999 - 1001
  • [24] The k-Distance Independence Number and 2-Distance Chromatic Number of Cartesian Products of Cycles
    Zehui Shao
    Aleksander Vesel
    Jin Xu
    Bulletin of the Malaysian Mathematical Sciences Society, 2018, 41 : 1377 - 1391
  • [25] The k-Distance Independence Number and 2-Distance Chromatic Number of Cartesian Products of Cycles
    Shao, Zehui
    Vesel, Aleksander
    Xu, Jin
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2018, 41 (03) : 1377 - 1391
  • [26] Distance two labelings of Cartesian products of complete graphs
    Lu, Damei
    Lin, Wensong
    Song, Zengmin
    ARS COMBINATORIA, 2012, 104 : 33 - 40
  • [27] Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs
    Shasha Ma
    Liancui Zuo
    Journal of Combinatorial Optimization, 2016, 32 : 725 - 740
  • [28] The (d, 1)-total labelling of square of cycles and their Cartesian products with bipartite graphs
    Zuo, Liancui
    Bai, Dan
    Shang, Chunhong
    ARS COMBINATORIA, 2019, 143 : 227 - 236
  • [29] Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs
    Ma, Shasha
    Zuo, Liancui
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32 (03) : 725 - 740
  • [30] More Results on the Domination Number of Cartesian Product of Two Directed Cycles
    Ye, Ansheng
    Miao, Fang
    Shao, Zehui
    Liu, Jia-Bao
    Zerovnik, Janez
    Repolusk, Polona
    MATHEMATICS, 2019, 7 (02)
12345