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

الموضوعات :

هادی رهبانی ¹ (گروه علوم و فناوری دفاعی، دانشگاه و پژوهشگاه عالی دفاع ملی و تحقیقات راهبردی، تهران، ایران)
سید نصیب الله دوستی مطلق ² (گروه علوم و فناوری دفاعی، دانشگاه و پژوهشگاه عالی دفاع ملی و تحقیقات راهبردی، تهران، ایران)
نادر جعفری راد ³ (گروه ریاضی دانشگاه شاهد، تهران، ایران)

تاريخ الإرسال : 27 الثلاثاء , محرم, 1442 تاريخ التأكيد : 18 الأحد , شوال, 1442 تاريخ الإصدار : 18 الجمعة , جمادى الثانية, 1443

الکلمات المفتاحية: Graph. Tree, Quantum secret sharing, Weak odd dominated set,

ملخص المقالة :

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

المصادر:

[1]	T. W. H. S. &. S. P. J. Haynes, Fundamentals of domination in graphs, New York: Marcel Dekker. Inc, 1998.
[2]	J. A. Telle, "Complexity of domination-type problems in graphs," Nord. J. Comput, vol. 1(1), pp. 157-171, 1994.
[3]	S. J. J. M. M. &. P. S. Gravier, "On weak odd domination and graph-based quantum secret sharing," Theoretical Computer Science, vol. 598, pp. 129-137, 2015.
[4]	]. D. Gottesman, "Theory of quantum secret sharing," Phys. Rev. A, vol. 61, p. 042311, 2000.
[5]	D. &. S. B. C. Markham, "Graph states for quantum secret sharing," Physical Review A, vol. 78(4), p. 042309, 2008.
[6]	D. M. M. S. E. Kashefi, "Information Flow in Secret Sharing Protocols," DCM 2009: Elec. Proc. Theor. Comp. Sci. , Vols. 9, 87, 2009.
[7]	D. C. a. S. Perdrix, "Parametrized Complexity of Weak Odd Domination Problems," In 19th International Symposium on Fundamentals of Computation Theory (FCT’13), LNCS. Springer, vol. 8070, p. 107–120, 2013.