روشی جدید برای پیداکردن یک کران بهبودیافته روی مجموعه مستقل ماکسیمال ومجموعه احاطه گر همبند مینیمال در گراف گوی واحد
محورهای موضوعی : تحقیق در عملیاتغلام حسن شیردل 1 * , مهدی جالینوسی 2
1 - گروه ریاضی، دانشکده علوم، دانشگاه قم، قم، ایران
2 - گروه ریاضی، دانشکده علوم، دانشگاه قم، قم، ایران
کلید واژه: کلمات کلیدی: مجموعه احاطه گر همبند- عدد استقلال &ndash, گراف گوی واحد- مجموعه مستقل ماکسیمال- عدد احاطه گرهمبند,
چکیده مقاله :
اندازه مجموعه مستقل ماکسیمال در یک گرافG را عدد استقلال می گوییم. اندازه مجموعه احاطه گر همبند مینیمال در گرافG را عدد احاطه گر همبند می گوییم. عدد استقلال را با α(G) و عدد احاطه گر همبند را با γ_c (G) نمایش می دهیم. از طرف دیگر ارتباط بین اندازه مجموعه مستقل ماکسیمال و اندازه مجموعه احاطه گر همبند مینیمال در یک گراف G بسیار اهمیت دارد. هدف اصلی این مقاله بهبود بخشیدن به کران بالای عدد استقلال وابسته به عدد احاطه گر همبند برای یک گراف گوی واحد است. بعلاوه ما کران بالای موجود تا کنون را بهبود داده ایم. کلمات کلیدی: مجموعه احاطه گر همبند- عدد استقلال گراف گوی واحد- مجموعه مستقل ماکسیمال- عدد احاطه گرهمبند
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