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 条
  • [11] On a Conjecture About Signed Domination in the Cartesian Product of Two Directed Cycles
    Zehui Shao
    Huiqin Jiang
    Mustapha Chellali
    Seyed Mahmoud Sheikholeslami
    Marzieh Soroudi
    Pu Wu
    Bo Wang
    Iranian Journal of Science and Technology, Transactions A: Science, 2019, 43 : 2541 - 2549
  • [12] On a Conjecture About Signed Domination in the Cartesian Product of Two Directed Cycles
    Shao, Zehui
    Jiang, Huiqin
    Chellali, Mustapha
    Sheikholeslami, Seyed Mahmoud
    Soroudi, Marzieh
    Wu, Pu
    Wang, Bo
    IRANIAN JOURNAL OF SCIENCE AND TECHNOLOGY TRANSACTION A-SCIENCE, 2019, 43 (A5): : 2541 - 2549
  • [13] Hyper-Hamiltonian Laceability of Cartesian Products of Cycles and Paths
    Yang, Yuxing
    COMPUTER JOURNAL, 2024, 67 (02) : 548 - 556
  • [14] Mutual-Visibility Sets in Cartesian Products of Paths and Cycles
    Korze, Danilo
    Vesel, Aleksander
    RESULTS IN MATHEMATICS, 2024, 79 (03)
  • [15] Mutual-Visibility Sets in Cartesian Products of Paths and Cycles
    Danilo Korže
    Aleksander Vesel
    Results in Mathematics, 2024, 79
  • [16] Channel assignment with separation in the Cartesian product of two cycles
    Vesel, A
    ITI 2002: PROCEEDINGS OF THE 24TH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY INTERFACES, 2002, : 505 - 510
  • [17] Group distance magic Cartesian product of two cycles
    Cichacz, Sylwia
    Dyrlaga, Pawel
    Froncek, Dalibor
    DISCRETE MATHEMATICS, 2020, 343 (05)
  • [18] Optimal L(2,1)-labeling of Cartesian products of cycles, with an application to independent domination
    Jha, PK
    IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-FUNDAMENTAL THEORY AND APPLICATIONS, 2000, 47 (10): : 1531 - 1534
  • [19] Extending partial edge colorings of iterated cartesian products of cycles and paths
    Casselgren, Carl Johan
    Granholm, Jonas B.
    Petros, Fikre B.
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2024, 26 (02) : 1 - 10
  • [20] On strict-double-bound graphs and Cartesian products of paths and cycles
    Egawa, Yoshimi
    Ogawa, Kenjiro
    Ozeki, Kenta
    Tagusari, Satoshi
    Tsuchiya, Morimasa
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2024, 16 (05)
12345