On an infinite family of graphs with information ratio \(2 - 1/k\) (Q2390949)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On an infinite family of graphs with information ratio \(2 - 1/k\) |
scientific article |
Statements
On an infinite family of graphs with information ratio \(2 - 1/k\) (English)
0 references
10 August 2009
0 references
The authors consider the problem of determining the information ratio of secret sharing schemes whose access structure is defined using a graph. In such case, the qualified subsets are those sets of vertices that span at least one edge, i.e. those vertex subsets that are not anticliques. The information ratio \(R(G)\) of a graph \(G\) is defined as the ratio of the greatest size of a share of a vertex and the size of the secret. The main result proved in the paper is the following. Let \(G\) be a graph of maximal degree \(k\) satisfying the following conditions: (A) every vertex has at most one neighbour of degree one; (B) vertices of degree at least 3 are not connected by an edge; (C) the girth of the graph is at least 6. The \(R(G)=2-1/k\).
0 references
secret sharing scheme
0 references
information ratio
0 references
access structure
0 references
entropy
0 references
graph theory
0 references