Skip to Main content Skip to Navigation
New interface
Journal articles

On weak odd domination and graph-based quantum secret sharing

Abstract : A weak odd dominated (WOD) 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 . We point out the connections of weak odd domination with odd domination, [σ,ρ]-domination, and perfect codes. We introduce bounds on κ(G), the maximum size of WOD sets of a graph G , and on κ′(G), the minimum size of non-WOD sets of G. Moreover, we prove that the corresponding decision problems are NP-complete.The study of weak odd domination is mainly motivated by the design of graph-based quantum secret sharing protocols: a graph G of order n corresponds to a secret sharing protocol whose threshold is κQ(G)=max⁡(κ(G),n−κ′(G)). These graph-based protocols are very promising in terms of physical implementation, however all such graph-based protocols studied in the literature have quasi-unanimity thresholds (i.e. κQ(G)=n−o(n) where n is the order of the graph G underlying the protocol). In this paper, we show using probabilistic methods the existence of graphs with smaller κQ (i.e. κQ(G)≤0.811n where n is the order of G). We also prove that deciding for a given graph G whether κQ(G)≤k is NP-complete, which means that one cannot efficiently double check that a graph randomly generated has actually a κQ smaller than 0.811n.
Document type :
Journal articles
Complete list of metadata
Contributor : Simon Perdrix Connect in order to contact the contributor
Submitted on : Thursday, December 31, 2015 - 10:04:06 AM
Last modification on : Wednesday, July 6, 2022 - 4:24:06 AM

Links full text



Sylvain Gravier, Jérôme Javelle, Mehdi Mhalla, Simon Perdrix. On weak odd domination and graph-based quantum secret sharing. Theoretical Computer Science, 2015, 598, ⟨10.1016/j.tcs.2015.05.038⟩. ⟨hal-01249271⟩



Record views