The Research On Properties And Algorithms Of [1,2]-Set In Graphs

In recent years, domination in graphs had become one of the most important research fields in graph theory. Some scholars found one of key technologies in wireless network-virtual backbone technology, which has close relation to connected dominating set in graphs. Since then, dom-inating set plays an important role in the study of wireless networks.The concept of [j, k]-set in graph has posed by Chellali et al in 2013. The study of [j,k]-sets, for j≥1,is motivated by the need to have dominat-ing sets, for example, acting as servers in a computing network, or acting as sets of monitoring devices in situations requiring surveillance, but with the need to establish such sets as efficiently or as cost effectively as possible, that is, without creating too much redundancy.In this dissertation, our study focus primarily on properties and al-gorithms of [1,2]-set and connected [1,2]-set in graphs. A dominating set S of graph G is called a [1,2]-set if for every vertex u∈V(G)\S, 1≤│N(v)∩S│≤2. The minimum cardinality of a [1,2]-set in G is called the [1,2]-domination number, abbreviated, [1,2]-number. If the reduced subgraph of [1,2]-set in G is connected, we called it by a connected [1,2]-set in G.Firstly, we consider the graphs G satisfy γ(G)=γ[1,2](G) and give some classes of graphs with this property-Spiders and generalized Pe-tersen graphs P(n,1).Secondly, we study the relation between [1,2]-set and connected [1,2]-set in graphs. We show some classes of graphs satisfy γc(G)=γc[1,2)(G) or yc[1,2](G)= n. We prove that Minimum Connected [1,2]-set Problem in Bipartite Graph is a NPC problem.Lastly, we consider the design of algorithms on [1,2]-number of a graph. Base on 0-1 programming, we design an algorithm to compute the exac-t [1,2]-number of a graph. As an example, we compute the [1,2]-number of some random generating tree by this algorithm. But computation complex-ity of this algorithm is O(2n). So we design two approximate algorithms to compute an approximate value of the [1,2]-number in trees by greedy strategy and compare their performances.