In this paper, we propose a new algorithm to find a minimum Connected Dominating Set(CDS) of Mobile Adhoc Network(MANET) modelled as a unit disk graph. The new algorithm known as New Connected Dominating Set(NCDS) reduces the number of message that needs to be broadcasted and thereby saving time and elongating lifetime of the network and also supports dynamic topology of the network. Further important theorems of Unit disk graph of the form (2n+8, 6n+14) , having degree (1≤deg≤6) for n ≥1 have been proposed and proved.

Mobile Adhoc Network (MANET), Connected Dominating Set (CDS), Unit Disk Graph (UDG).

[1] S. Guha, and. S. Khuller, “Approximation Algorithms for Connected Dominating Sets”, Algorithmica Vol. 20, 4, pp. 374-387, 1998.
[2] X. Yan , Y.Sun,Y.Wang, “A Heuristic Algorithm for Minimum Connected Dominating Set with Maximal Weight in Ad Hoc Networks”, M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 719–722, 2004. © Springer-Verlag Berlin Heidelberg 2004
[3] O. Chaturvedi, P Kaur, N Ahuja, T. Prakash, “Improved Algorithms for Construction of Connected Dominating Set in MANETs”, 2016 6th International Conference - Cloud System and Big Data Engineering (Confluence), 978-1-4673-8203-8/16/$31.00_c 2016 IEEE
[4]K..G. Preetha, A. Unnikrishnan , “ Enhanced domination set based routing in mobile ad hoc networks with reliable nodes”, @2017 Published by Elsevier Ltd.
[5]P.S..Vinayagam, “A Survey of Connected Dominating Set Algorithms for Virtual Backbone Construction in Ad Hoc Networks”, International Journal of Computer Applications (0975 – 8887) Volume 143 – No.9, June 2016
[6] K..G. Preetha, A. Unnikrishnan, “Improving the Routing Performance of Mobile Ad hoc Networks Using Domination Set”, International Conference on Information and Communication Technologies (ICICT 2014)
[7]K.Islam, S.G, Akl, H..Meijer, “Maximizing the Lifetime of Wireless Sensor Networks through Domatic Partition”, 2009 IEEE 34th Conference on Local Computer Networks (LCN 2009) Zürich, Switzerland; 20-23 October 2009
[8] B.Yin, H. Shi, Yi. Shang, “An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks”, Journal of Parallel and Distributed Computing archive, Volume 71 Issue 1, January, 2011, Pages 27-39
[9] J. Wu, H. L. Li, “On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks”, Proc. of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7-14, Aug. 1999.
[10] B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, “Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” ACM Wireless Networks J., vol. 8, no. 5, pp. 481-494, Sept. 2002.
[11] M.Avula, S.M. Yoo, S Park , “Constructing Minimum Connected dominating Set in Mobile Adhoc Networks, International Journal of applications of graph theory in wireless ad hoc network and sensor networks” (GRAPH-HOC)Vo4, No 23,September 2012.