New bounds on weak odd dominating set in trees

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.

* The formulas are not displayed correctly.