On Weak Odd Domination and Graph-based Quantum Secret Sharing

Details On Weak Odd Domination and Graph-based Quantum Secret Sharing On Weak Odd Domination and Graph-based Quantum Secret Sharing

2011-12-12

arxiv.org/abs/1112.2495v1

Computer Science

Computational Complexity

Subsumes arXiv:1109.6181: Optimal accessing and non-accessing structures for graph protocols

Scientific paper

A weak odd dominated (WOD) set in a graph is a subset B of vertices such that there exists a disjoint subset D such that all vertices in B have an odd number of neighbors in D. We point out the connections of weak odd domination with odd domination, (\sigma,\rho)-domination, and perfect codes. We introduce bounds on \kappa(G), the maximum size of WOD sets of a graph G, and on \kappa'(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 introduced by Markham and Sanders. Indeed, a graph G of order n can be used to define a quantum secret sharing protocol where \kappa_Q(G) = max(\kappa(G), n-\kappa'(G)) is a threshold ensuring that any set of more than \kappa_Q(G) players can recover the quantum secret. We show the hardness of finding the optimal threshold of a graph-based quantum secret sharing protocol. Finally, using probabilistic methods, we show the existence of an infinite family of graphs with `small' \kappa_Q, and that with high probability a random graph G of order n satisfies \kappa_Q(G)< 0.87n.

Affiliated with

Also associated with

No associations

Rating

On Weak Odd Domination and Graph-based Quantum Secret Sharing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Weak Odd Domination and Graph-based Quantum Secret Sharing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Weak Odd Domination and Graph-based Quantum Secret Sharing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-708731