Mathematics – Combinatorics
Scientific paper
2011-02-25
Mathematics
Combinatorics
Scientific paper
In graph theoretical models of the spread of disease through populations, the spread of opinion through social networks, and the spread of faults through distributed computer networks, vertices are in two states, either black or white, and these states are dynamically updated at discrete time steps according to the rules of the particular conversion process used in the model. This paper considers the irreversible k-threshold and majority conversion processes. In an irreversible k-threshold (resp., majority) conversion process, a vertex is permanently colored black in a certain time period if at least k (resp., at least half) of its neighbors were black in the previous time period. A k-conversion set (resp., dynamic monopoly) is a set of vertices which, if initially colored black, will result in all vertices eventually being colored black under a k-threshold (resp., majority) conversion process. We answer several open problems by presenting bounds and some exact values of the minimum number of vertices in k-conversion sets and dynamic monopolies of complete multipartite graphs, as well as of Cartesian and tensor products of two graphs.
Adams Sarah Spence
Brass Zachary
Stokes Connor
Troxell Denise Sakai
No associations
LandOfFree
Irreversible k-threshold and majority conversion processes on complete multipartite graphs and graph products does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Irreversible k-threshold and majority conversion processes on complete multipartite graphs and graph products, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Irreversible k-threshold and majority conversion processes on complete multipartite graphs and graph products will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-302000