فرض کنید G=(V,E) یک گراف و f:V(G)→{0,1,2} یک تابع باشد. رأسv نسبت به تابعf محافظتشده است هرگاه f(v)>0 یا f(v)=0و v با رأسی به وزن مثبت مجاور باشد. تابع f، یک تابع احاطهگر هم-رومی (به اختصار CRDF) است هرگاه: (1) هر رأس
چکیده کامل
فرض کنید G=(V,E) یک گراف و f:V(G)→{0,1,2} یک تابع باشد. رأسv نسبت به تابعf محافظتشده است هرگاه f(v)>0 یا f(v)=0و v با رأسی به وزن مثبت مجاور باشد. تابع f، یک تابع احاطهگر هم-رومی (به اختصار CRDF) است هرگاه: (1) هر رأس درV محافظتشده باشد، و (2) هر رأسu∈V با وزن مثبت همسایهای همچون v∈Vبا f(v)=0 داشتهباشد به طوریکه تابعf_uv:V→{0,1,2} تعریفشده بهصورت f_uv (u)=f(u)-1 ، f_uv (v)=1 و برایx∈V-\{v,u} بهصورت f_uv (x)=f(x)، هیچ رأس محافظتنشدهای نداشتهباشد. وزنf بهصورت ω(f)=∑_(v∈V)▒〖f(v)〗 تعریف میشود. عدد احاطهای هم-رومی گراف G که با نماد γ_cr G) نمایش داده میشود، کمترین وزن در بین تمامی توابع احاطهگر هم-رومی گراف G میباشد. در این مقاله، ابتدا یک کران بالا برای عدد احاطهای هم-رومی درختها برحسب تعداد رئوس، تعداد برگها و تعداد رئوس تکیهگاه درخت T ارائه میکنیم. همچنین ما کرانهایی برای عدد احاطهای هم-رومی یک درخت برحسب مرتبه و سایر پارامترهای احاطهای آن بهدست میآوریم.
پرونده مقاله