Optimal accessing and non-accessing structures for graph protocols
arXiv:1109.6181
Abstract
An accessing set in a graph is a subset B of vertices such that there exists D subset of B, such that each vertex of V\B has an even number of neighbors in D. In this paper, we introduce new bounds on the minimal size kappa'(G) of an accessing set, and on the maximal size kappa(G) of a non-accessing set of a graph G. We show strong connections with perfect codes and give explicitly kappa(G) and kappa'(G) for several families of graphs. Finally, we show that the corresponding decision problems are NP-Complete.
References in corpus (6)
- Multi-party entanglement in graph states
- Graph States for Quantum Secret Sharing
- Classical simulation versus universality in measurement based quantum computation
- Finding Optimal Flows Efficiently
- New Protocols and Lower Bound for Quantum Secret Sharing with Graph States
- Classical versus Quantum Graph-based Secret Sharing