Improvment Upper Bound of the Independence Nnmber of Maximum Independent Set in Unit Disk Graph

Subject Areas : Statistics

Gholam Hassan Shirdel ¹ , mehdi jalinousi ²

1 - Department of Mathematics, Faculty of Science, University of Qom, Qom, Iran
2 - Department of Mathematics, Faculty of Science, University of Qom, Qom, Iran

Received: 2020-12-31 Accepted : 2022-10-03 Published : 2022-12-22

Keywords: مجموعه احاطه گر همبند- عدد استقلال &ndash, گراف دیسک واحد- مجموعه مستقل ماکسیمال- عدد احاطه گرهمبند,

Abstract :

In a unit disk graph two vertices are adjacent if the distance between them is less than or equal to one with a two-dimensional Euclidean meter. The size of the maximal independent set in a graph G is called the independent number denoted by α(G). The size of the minimal connected dominating set in a graph G is called the connected domination number denoted by γ_c^((G)). A subset S of vertices in a graph is called a dominating set if every vertex is either in the subset or adjacent to a vertex in the S. A dominating set is connected if it induces a connected subgraph. A connected dominating set is often used as a virtual backbone in wireless sensor networks to improve communication and storage performance. Clearly the smaller virtual backbone gives the better performance.However computing a minimal connected dominating set is NP-hard. In other hand relation between the size of the minimal connected dominating set in a graph G is very important. The aim of this paper is to determine two better upper bounds of the independence number dependent on the connected domination number for a unit disk graph. Further we improve the upper bound to obtain the best bound with respect to the upper bounds obtained thus far.

References:

[1]	C. C. J. J. D. S. ‎‎‎‎‎‎‎‎‎Clark B. N., "Unit disk graphs," Discrete Mathematics, 86, pp. 165-177, 1990.
[2]	Wan P . J., Alzoubi K. M., Frierder o., "Distributed constrution on of connected dominating set in wireless  ad hoc networks," ACM/  Springer Mobile Network , pp. 141-149, 2004.
[3]	Wan P. J., Wang L., Yao F.F.,s ‎ "Two phased approximation algorithm s for minium CDS in wirelees ad hoc networks ICDCS," IEEE, pp. 3374-344, 2008.
[4]	K. A. M. U. S. M. ‎‎‎‎‎‎‎‎‎Funke S., "Asimple improved distributed algorithm for minimum CD S in unit disk graphs," ACM T rans. Sensor N et, pp. 4444-453, 2006.
[5]	D. Dai and C. Yu, "A (5 +€)-approximation algorithm for  minimum weighted dominatings set in unit disk graph ," Theor. Com put. Sci., p. 756–765, 2009.
[6]	Wu W., Du H., jia X., Li Y., Huang S., "Minimum c onnected dominating sets and maximal independent sets in unit disk graphs," Theor. Comput. Sci., pp. 1-7, 2006.    Li M., Wan P.J., Yao F., "Tighter Approximation Bonds for Minimum CDS in Unit Disk Graphs," Algorithmica 61(4),  pp. 1000-1021, 2011. 2, 10, 12, 13, 29