Unit disk graph and wireless sensor networks

Let G = (V;E) be a graph with node set V = V (G) and edge set E = E(G). A graph G = (V;E) is said to be a unit disk graph if the Euclidean distanced(u; v) 1 is equivalence of existence an edge between two nodes u and v. The unit disk graph is a mathematical model for wireless sensor networks when all sensors have the same communication radius. Maximal independent set of nodes, that is also a dominating set, and minimum connected dominating set are two mathematical tools in this area. The size of the maximum inde- pendent set (MIS), and the size of the minimum connected dominating set (MIN-CDS) in a graph G, are denoted by (G) and c(G) respectively. The ratio of (G) with c(G) gives a theoretical upper bound for approximation the connected domination number in a unit disk graph. In this talk, we opti- mize this mathematical model by improving relationship between (MIS), and (MIN-CDS).