Target Set Selection On Graphs

Target Set Selection(TSS)was initially proposed by Kempe et al.to study the social network analysis involving the problem of the spread of information,ideas or influence through a social network.This model can also formulate many problems arising in economy,sociology,medicine and computer science and,therefore,receives much attention from both theoretical and practical interests.For Target Set Selection problem,a network is mathematically modeled as an undirected graph with its vertices equipped with a threshold function θ(v):V(G)→N,where V(G)is the vertex set of G and N,the set of positive integers.A 9-activation of a vertex in TSS is defined via the course of a dynamic process,namely the θ-activation process:at phase 0 of the process,we select an initial set S of vertices to be active while all other vertices are inactive.Starting from S,at every phase i>0,vertices become active according to the following rule:Sequential updating rule:Choose exactly one inactive vertex v that has at least θ(v)already-active neighbors to become active.Once a vertex becomes active,it remains active for the entire process.If a set S of vertices can activates all the vertices of G in an activation process then we call S a θ-target set of G.The goal of Target Set Selection(TSS)is to select a 0-target set S with minimum number of vertices.The cardinality of such S is called the θ-target number of G and denoted by mine(G).In Target Set Selection problem,various types of thresholds were introduced to meet some specific requirements.In particular,the threshold θ(v)=d(v)-1 has a close relation to the ’vertex feedback problem’,also known as the hitting cycle problem’ or ’decycling problem’.It is known that the Target Set Selection problem is NP-hard even for bounded bipartite graphs.Therefore,much research interests on this subject focus on particular graph structures,e.g.,block-cactus graph,chordal graph and Hamming graph,chordal ring,tori,hexagonal grid,sparse graph and ’cliquish’graph;tree,multipartite graph and grid.The dissertation includes six chapters summarized as follows:The first chapter gives some basic definitions,notations involved in the thesis,and gives an overview of the previous work in the literatures and our main work in the thesis.In the second chapter,we give a characterization of those plane graphs G for which mina(G)= 3.Consequently,we show that the minimum degree of such plane graphs is at most 4.In Chapter 3 we establish an upper bound on the k-target number mink(G□H)in terms of that of G and H for general k,which improves the upper bound established by Adams et al.In particular,a lower bound and a much tight upper bound for k = 2 are also given and the latter is attained by almost all the Cartesian product graphs G□H for which mine(G□H)is known in the literatures.In chapter 4 and chapter 5,we focus on some particular grids including planar,cylindrical,toroidal,Mobious quadrilateral grids and triangular grids for θ = 2,3,4.In the last chapter,we give a connection between zero forcing set and connected dominating set and give a proof for Davila’s conjecture on zero forcing number.