ﮐﺮان ﻫﺎي ﺟﺪﯾﺪ ﺑﺮاي ﻋﺪد اﺣﺎﻃﻪ ﮔﺮ ﺿﻌﯿﻒ ﻓﺮد روي درﺧﺖﻫﺎ

New bounds on weak odd dominating set in trees

ﯾﮏ ﻣﺠﻤﻮﻋﻪ اﺣﺎﻃﻪﮔﺮ ﺿﻌﯿﻒ ﻓﺮد در ﯾﮏ ﮔﺮاف زﯾﺮ ﻣﺠﻤﻮﻋﻪاﯾﯽ ﻣﺎﻧﻨﺪ B از رﺋﻮس ﻣﯽﺑﺎﺷﺪ ﺑﻪﻃﻮري ﮐﻪ ﻣﺠﻤﻮﻋﻪ ﻣﺘﻤﺎﯾﺰ C از رﺋﻮس وﺟﻮد داﺷﺘﻪ ﺑﺎﺷﺪ ﮐﻪ ﻫﺮ رأس B داراي ﺗﻌﺪادي ﻓﺮد ﻫﻤﺴﺎﯾﻪ در C ﺑﺎﺷﺪ. ﺑﯿﺸﺘﺮﯾﻦ اﻧﺪازه ﺑﯿﻦ ﻣﺠﻤﻮﻋﻪﻫﺎي اﺣﺎﻃﻪﮔﺮ ﺿﻌﯿﻒ ﻓﺮد در ﮔﺮاف 𝐺 را ﺑﺎ 𝑘 و ﮐﻤﺘﺮﯾﻦ اﻧﺪازه در ﺑﯿﻦ ﻣﺠﻤﻮﻋﻪﻫﺎﯾﯽ ﮐﻪ اﺣﺎﻃﻪﮔﺮ ﺿﻌﯿﻒ ﻓﺮد ﻧﯿﺴﺘﻨﺪ را ﺑﺎ )𝑘􀀁 𝐺 ﻧﺸﺎن ﻣﯽدﻫﻨﺪ. از اﻧﮕﯿﺰهﻫﺎي اﺻﻠﯽ ﻣﻄﺎﻟﻌﻪ و ﺑﺮرﺳﯽ ﻣﺠﻤﻮﻋﻪﻫﺎي اﺣﺎﻃﻪﮔﺮ ﺿﻌﯿﻒ ﻓﺮد ﻃﺮاﺣﯽ ﭘﺮوﺗﮑﻞ ﺗﺴﻬﯿﻢ راز ﮐﻮاﻧﺘﻮﻣﯽ ﻣﺒﺘﻨﯽ ﺑﺮ ﮔﺮافﻫﺎ ﻣﯽﺑﺎﺷﺪ. ﮔﺮاف 𝐺 از ﻣﺮﺗﺒﻪ 𝑛 ﻣﺘﻨﺎﻇﺮ ﺑﺎ ﯾﮏ ﭘﺮوﺗﮑﻞ ﺗﺴﻬﯿﻢ راز ﺑﺎ آﺳﺘﺎﻧﻪ })𝑘􀀂(𝐺) = max {𝑘(𝐺), 𝑛 − 𝑘􀀁(𝐺 ﻣﯽﺑﺎﺷﺪ. در اﯾﻦ ﻣﻘﺎﻟﻪ ﻣﺎ ﯾﮏ ﮐﺮان ﭘﺎﯾﯿﻦ ﺑﺮاي ﺑﯿﺸﺘﺮﯾﻦ اﻧﺪازه ﯾﮏ ﻣﺠﻤﻮﻋﻪ اﺣﺎﻃﻪﮔﺮ ﺿﻌﯿﻒ ﻓﺮد در درﺧﺖﻫﺎ اراﯾﻪ ﻣﯽدﻫﯿﻢ و ﯾﮏ ﺣﺪس اراﯾﻪ ﺷﺪه در اﯾﻦ ﺧﺼﻮص را در درﺧﺖﻫﺎ اﺛﺒﺎت ﻣﯽﮐﻨﯿﻢ. ﻫﻤﭽﻨﯿﻦ ﯾﮏ ﮐﺮان ﺑﺎﻻ ﺑﺮاي ﺑﯿﺸﺘﺮﯾﻦ اﻧﺪازه ﯾﮏ ﻣﺠﻤﻮﻋﻪ اﺣﺎﻃﻪﮔﺮ ﺿﻌﯿﻒ ﻓﺮد در درﺧﺖﻫﺎ ﺑﺮاﺳﺎس ﻣﺮﺗﺒﻪ و ﺗﻌﺪاد ﺑﺮگ ﻫﺎ اراﯾﻪ ﻣﯽﮐﻨﯿﻢ و ﺑﺮﺧﯽ از ﮐﺮانﻫﺎي ﻣﻮﺟﻮد ﻗﺒﻠﯽ را ﺑﻬﺒﻮد ﻣﯽدﻫﯿﻢ .

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.