احاطه گر k-مجاورت در گراف ها

فرض کنید G یک گراف ساده و بدون دور با مجموعه رئوس V باشد. یک مجموعه S که زیرمجموعه V است را احاطه گر گویند هرگاه هر راسی که خارج از S است با حداقل یک راس در S همجوار باشد. فرض کنید k≥۱ عددی صحیح باشد. مجموعه احاطه گر S را یک مجموعه احاطه گر k-مجاورت می نامیم هرگاه زیرگراف القائی G[S] شامل راسی از درجه حداکثر k-۱ باشد. کمترین تعداد عناصر یک مجموعه احاطه گر k-مجاورت برای گراف G عدد احاطه k-مجاورت آن گراف نامیده می شود و با نماد γ_k^a (G) نمایش داده می شود. در این مقاله، مطالعه احاطه گر k-مجاورت آغاز می شود. سپس مقادیر دقیق و کران هایی برای عدد احاطه k-مجاورت یک گراف داده شده ارائه می شود. همچنین، نشان داده می شود که یک الگوریتم با زمان چندجمله ای برای محاسبه عدد احاطه k-مجاورت یک درخت داده شده وجود دارد. علاوه بر این، ثابت می شود که مسئله تصمیم گیری مرتبط با احاطه گر k-مجاورت برای گراف های دوبخشی NP-کامل است.

کلیدواژه ها:

مجموعه احاطه گر ، گراف ، عدد احاطه