فهرست نشریات علمی دسترسی آزاد ایران

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