کران های جدید برای عدد احاطه گر ضعیف فرد روی درخت ها
یک مجموعه احاطه گر ضعیف فرد در یک گراف زیر مجموعه ایی مانند B از ریوس می باشد به طوری که مجموعه متمایز C از ریوس وجود داشته باشد که هر راس B دارای تعدادی فرد همسایه در C باشد. بیشترین اندازه بین مجموعه های احاطه گر ضعیف فرد در گراف G را با k(G) و کمترین اندازه در بین مجموعه هایی که احاطه گر ضعیف فرد نیستند را با k^' (G) نشان می دهند. از انگیزه های اصلی مطالعه و بررسی مجموعه های احاطه گر ضعیف فرد طراحی پروتکل تسهیم راز کوانتومی مبتنی بر گراف ها می باشد. گراف G از مرتبه n متناظر با یک پروتکل تسهیم راز با آستانه k_Q (G)=max{k(G),n-k^' (G)} می باشد. در این مقاله ما یک کران پایین برای بیشترین اندازه یک مجموعه احاطه گر ضعیف فرد در درختها ارایه می دهیم و یک حدس ارایه شده در این خصوص را در درختها اثبات می کنیم. همچنین یک کران بالا برای بیشترین اندازه یک مجموعه احاطه گر ضعیف فرد در درختها بر اساس مرتبه و تعداد برگ ها ارایه می کنیم و برخی از کرانهای موجود قبلی را بهبود می دهیم.
* فرمول ها به درستی نمایش داده نمی شوند.
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.