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

Chun-Ying Chiang (), Wei-Ting Huang () and Hong-Gwa Yeh ()
Additional contact information
Chun-Ying Chiang: National Central University
Wei-Ting Huang: National Central University
Hong-Gwa Yeh: National Central University

Journal of Combinatorial Optimization, 2016, vol. 31, issue 2, No 22, 815-832

Abstract: Abstract 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$$ 2 n 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.

Keywords: Dynamos; Feedback vertex set; Target set selection; Irreversible k-threshold; Viral marketing; Social networks (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9790-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:2:d:10.1007_s10878-014-9790-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9790-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().