احاطه گر k-مجاورت در گراف ها
فرض کنید 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-کامل است.
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.