A New Method for Finding an Improved Bound on the Maximal Independent Set and Minimal Connected Dominating Set in the Unit Ball Grph
Subject Areas : تحقیق در عملیاتGholam Hassan Shirdel 1 , mehdi jalinousi 2
1 - Department of Mathematics, Faculty of Science, University of Qom, Qom, Iran
2 - Department of Mathematics, Faculty of Science, University of Qom, Qom, Iran
Keywords: Keywords: Connected dominating set, Independent number, Unit ball graph, Maximal independent set, Connected domination number.,
Abstract :
A New Method for Finding an Improved Bound on the Maximal Independent Set and Minimal Connected Dominating Set in the Unit Ball Grph Abstract The size of maximum independent set in a graph G is called the independence number. The size of the minimum connected dominating set in G is called the connected domination number. The independent number denoted by α(G) and the connected domination number denoted by γ_c (G). In other hand relation between the size of the maximal independent set and 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 ball graph. Further we improve the upper bound to obtain the best bound with respect to the upper bounds obtained thus far. Keywords: Connected dominating set, Independent number, Unit ball graph, Maximal independent set, Connected domination number.
[1] Du D. Z., Wan P. J., Connected Dominating Set, Theory and Applications,Springer,Optimization and Its Applications 77, New York, 2013. 3, 15, 29
[2] Butenko S., Kahruman A. S.,Ursulenko O., On connected domination in unit ball graphs, Optim. Lett. 5(2), pp. 195–205, 2011. 1, 15
[3] Kim D., Zhang Z., Li X., Wang W.,Wu ., Du D. Z., A betterapproximation algorithm for compoting connected dominating sets in unit ball graphs, IEEE Trans. Mobilee compot.9(8), pp. 1108-1118, 2010. 15, 16, 18, 19.
[4] Mojdeh D.A., R am ezan i M.,Ghanbari M.,A new approxim ation of the bound of independence number in UDG, IMC44,University of Ferdowsi, August 27-30, Mashhad, Iran, 2013. 10, 12, 16
