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