کران های جدید برای عدد احاطه گر ضعیف فرد روی درخت ها

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

* فرمول ها به درستی نمایش داده نمی شوند.