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

NCU Institutional Repository > 理學院 > 數學系 > 期刊論文 > Item 987654321/109186

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://ir.lib.ncu.edu.tw/handle/987654321/109186

题名:	Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis
作者:	葉鴻國;Chiang, Chun-Ying;Huang, Wei-Ting;Yeh, Hong-Gwa
贡献者:	理學院數學系
关键词:	Combinatorics;Convex and Discrete Geometry;Mathematical Modeling and Industrial Mathematics;Mathematics;Mathematics and Statistics;Operations Research/Decision Theory;Optimization;Theory of Computation
日期:	2016-02-01
上传时间:	2026-04-23 16:14:13 (UTC+8)
出版者:	Springer Netherlands;New York: Springer US
摘要:	摘要： 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 2 n 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 . 其他題名： J Comb Optim 出版者： New York: Springer US 出版日期： 2016-02-01 出處： Journal of combinatorial optimization, 2016-02, Vol.31 (2), p.815-832 版權： Springer Science+Business Media New York 2014 識別號： ISSN: 1382-6905 識別號： EISSN: 1573-2886 識別號： DOI: 10.1007/s10878-014-9790-5
显示于类别:	[數學系] 期刊論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	18	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....