On an infinite family of graphs with information ratio \(2 - 1/k\) (Q2390949)

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\).