|
Abstract
|
تابع f از V(G) به {0,1,2} را یک تابع {2}-احاطه گر گوییم, هرگاه به ازای هر راس v از V(G) که f(v)<1 یا f(v)=1 داشته باشیم: f(N[v])>2 یا f(N[v])=2. در این طرح خواص پارامترهایی مورد بررسی قرار می گیرند که در آن ها عدد 2 به کار رفته است. برخی از آن ها عبارتند از: عدد احاطه ای {2}-مستقل بیرونی و عدد شبه رومی مستقل رومی. ما ضمن تعیین کران های بالا و پایین برای آن ها, برخی کران های قابل وصول را معرفی کرده و در ادامه رابطه این پارامترها با سایر پارامترهای احاطه ای از قبیل عدد احاطه ای رومی مستقل بیرونی و رومی مضاعف مستقل بیرونی را مورد بررسی قرار می دهیم. همچنین روابط نوردهاوس-گادم و NP سختی را برای پارامترهای ذکر شده مورد مطالعه قرار می دهیم.
|