Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis
| Autor: | Chun-Ying Chiang, Wei-Ting Huang, Hong-Gwa Yeh |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
021103 operations research Control and Optimization Applied Mathematics 0211 other engineering and technologies Generalized Petersen graph Torus 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science Applications Vertex (geometry) Combinatorics Computational Theory and Mathematics Computer Science::Discrete Mathematics 010201 computation theory & mathematics Petersen family Theory of computation Discrete Mathematics and Combinatorics Permutation graph Feedback vertex set Nabla symbol Mathematics |
| Zdroj: | Journal of Combinatorial Optimization. 31:815-832 |
| ISSN: | 1573-2886 1382-6905 |
| DOI: | 10.1007/s10878-014-9790-5 |
| Popis: | In this paper, we use the connection between dynamic monopolies and feedback vertex sets to establish explicit formulas and new bounds for decycling number $$\nabla (G)$$?(G) when $$G$$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$$G is a cycle permutation graph or a generalized Petersen graph on $$2n$$2n vertices, then $$\nabla (G)=\lceil (n+1)/2\rceil $$?(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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink