 |
پشتیبانی: ۰۲۱۹۱۰۹۰۸۹۱ support@magiran.com |
تاریخ چاپ: ۱۴۰۴/۰۵/۲۲ |
| این مقاله در «بانک اطلاعات نشریات کشور» به نشانی magiran.com/p2458045 نمایه شده است. برای مطالعه متن آن به سایت مراجعه کنید. |
| کران های جدید برای عدد احاطه گر ضعیف فرد روی درخت ها | |
| نویسنده(گان): | هادی رهبانی*، سید نصیب الله دوستی مطلق، نادر جعفری راد |
|
چکیده: |
یک مجموعه احاطه گر ضعیف فرد در یک گراف زیر مجموعه ایی مانند B از ریوس می باشد به طوری که مجموعه متمایز C از ریوس وجود داشته باشد که هر راس B دارای تعدادی فرد همسایه در C باشد. بیشترین اندازه بین مجموعه های احاطه گر ضعیف فرد در گراف G را با k(G) و کمترین اندازه در بین مجموعه هایی که احاطه گر ضعیف فرد نیستند را با k^' (G) نشان می دهند. از انگیزه های اصلی مطالعه و بررسی مجموعه های احاطه گر ضعیف فرد طراحی پروتکل تسهیم راز کوانتومی مبتنی بر گراف ها می باشد. گراف G از مرتبه n متناظر با یک پروتکل تسهیم راز با آستانه k_Q (G)=max{k(G),n-k^' (G)} می باشد. در این مقاله ما یک کران پایین برای بیشترین اندازه یک مجموعه احاطه گر ضعیف فرد در درختها ارایه می دهیم و یک حدس ارایه شده در این خصوص را در درختها اثبات می کنیم. همچنین یک کران بالا برای بیشترین اندازه یک مجموعه احاطه گر ضعیف فرد در درختها بر اساس مرتبه و تعداد برگ ها ارایه می کنیم و برخی از کرانهای موجود قبلی را بهبود می دهیم. * فرمول ها به درستی نمایش داده نمی شوند. |
| کلیدواژگان: | مجموعه احاطه گر ضعیف فرد، تسهیم راز کوانتومی، گراف، درخت |
| نوع مقاله: | مقاله پژوهشی/اصیل |
| زبان: | انگلیسی |
| انتشار در: | مجله پژوهش های نوین در ریاضی، پیاپی ۳۴ (بهمن و اسفند ۱۴۰۰) |
| صفحات: | ۱۷۹ -۱۸۸ |
| نسخه الکترونیکی: | متن این مقاله در سایت مگیران قابل مطالعه است. |
| New bounds on weak odd dominating set in trees | |
| Author(s): | Hadi Rahbani *، Sayed N .Doustimotlagh، Nader Jafari Rad |
|
Abstract: |
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.
|
| Keywords: | Weak odd dominated set، Quantum secret sharing، Graph. Tree |
| Article Type: | Research/Original Article |
| Language: | English |
| Published: | New research in Mathematics, Volume:7 Issue: 34, 2022 |
| Pages: | 179 -188 |
| Full text: | PDF is available on the website. |