Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis

Chun Ying Chiang, Wei Ting Huang, Hong Gwa Yeh

研究成果: 雜誌貢獻期刊論文同行評審

1 引文 斯高帕斯(Scopus)

摘要

In this paper, we use the connection between dynamic monopolies and feedback vertex sets to establish explicit formulas and new bounds for decycling number ∇(G) when G is one of the following classes of graphs: cycle permutation graphs, generalized Petersen graphs, and torus cordalis. In the first part of this paper, we show that if G is a cycle permutation graph or a generalized Petersen graph on 2n vertices, then ∇(G)=⌈(n+1)/2⌉. These results extend a recent result by Zaker (Discret Math 312:1136–1143, 2012) and partially answer a question of Bau and Beineke (Australas J Comb 25:285–298, 2002). Note that our definition of a generalized Petersen graph is more general than the one used in Zaker (Discret Math 312:1136–1143, 2012). The second and major part of this paper is devoted to proving new upper bounds and exact values on the size of the minimum feedback vertex set and minimum dynamic monopoly for torus cordalis. Our results improve the previous results by Flocchini in 2004.

原文???core.languages.en_GB???
頁(從 - 到)815-832
頁數18
期刊Journal of Combinatorial Optimization
31
發行號2
DOIs
出版狀態已出版 - 1 2月 2016

指紋

深入研究「Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis」主題。共同形成了獨特的指紋。

引用此