بهبود کران بالای عدد استقلال مجموعه مستقل ماکزیمال در گراف دیسک واحد

در یک گراف دیسک واحد دو راس مجاورند اگر با متر اقلیدسی دو بعدی فاصله بین آنها کوچکتر یا مساوی یک باشد. اندازه مجموعه مستقل ماکسیمال در یک گرافG را عدد استقلال گفته و با α(G) نشان می دهیم. اندازه مجموعه احاطه گر همبند مینیمال در گراف G را عدد احاطه گر همبند می گفته و با γ_c (G) نمایش می دهیم. واضح است اگر فاصله بین دو گره از یک گراف دیسک واحد بیشتر از یک باشد آن دو گره مسقل هستند. یک زیر مجموعه S از راس ها در یک گراف مجموعه احاطه گر نامیده می شود اگر هر راس از گراف G یا عضو مجموعه S باشد یا با عضوی از آن مجاور باشد. یک مجموعه احاطه گر همبند است اگر یک زیر گراف همبند القا کند. یک مجموعه احاطه گر همبند اغلب به عنوان یک دکل مجازی در شبکه های سنسور بی سیم جهت بهبود ارتباطات و کارایی یهتر استفاده می شود. واضح است که دکل مجازی کوچکتر کارایی بهتری دارد. با این حال محاسبه یک مجموعه احاطه گر همبند مینیمال همچنان NP-سخت است. از طرفی ارتباط بین اندازه مجموعه مستقل ماکسیمال و اندازه مجموعه احاطه گر همبند مینیمال در یک گراف G بسیار اهمیت دارد. هدف اصلی این مقاله بهبود بخشیدن به کران بالای عدد استقلال وابسته به عدد احاطه گر همبند برای یک گراف دیسک واحد است. بعلاوه ما کران بالای موجود تا کنون را بهبود داده ایم.