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

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