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

محورهای موضوعی : آمار

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

تاریخ دریافت : 1399/06/25 تاریخ پذیرش : 1400/03/09 تاریخ انتشار : 1400/11/01

کلید واژه: 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)} می‌باشد. در این مقاله ما یک کران پایین برای بیشترین اندازه یک مجموعه‌ احاطه‌گر ضعیف فرد در درختها ارایه می دهیم و یک حدس ارایه شده در این خصوص را در درختها اثبات می کنیم. همچنین یک کران بالا برای بیشترین اندازه یک مجموعه‌ احاطه‌گر ضعیف فرد در درختها بر اساس مرتبه و تعداد برگ‌ها ارایه می کنیم و برخی از کرانهای موجود قبلی را بهبود می دهیم.

چکیده انگلیسی:

A weak odd dominating set in a graph is a subset B of vertices for which there exists a distinct set of vertices C such that every vertex in B has an odd number of neighbors in C. κ(G) denotes the size of the largest weak odd dominating set and κ'(G) the size of the smallest non weak odd dominating set. One of main motivation for studying the weak odd dominating set is their role in the design of graph-based quantum secret sharing protocols. Graph G of order n corresponds to a secret sharing protocol whose threshold is κ_Q (G)=max(κ(G),n- κ'(G)). In this paper we prove a lower bound for the largest weak odd dominating set in trees proving a conjecture for trees. Also, we present an upper bound for the largest weak odd dominating set in trees in terms of the order and the number of leaves and we improve some previous bounds.

منابع و مأخذ:

[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.