New bounds on weak odd dominating set in trees

Subject Areas : Statistics

Hadi Rahbani ¹ (Department of Defense Science and Technology, National Defense and Strategic Research University and Research Institute, Tehran, Iran)
Sayed N .Doustimotlagh ² (Department of Defense Science and Technology, National Defense and Strategic Research University and Research Institute, Tehran, Iran)
Nader Jafari Rad ³ (Department of Mathematics, Shahid University, Tehran, Iran)

Received: 2020-09-15 Accepted : 2021-05-30 Published : 2022-01-21

Keywords: مجموعه احاطه‌گر ضعیف فرد, گراف, تسهیم راز کوانتومی, درخت,

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.

References:

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