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
    0 references
    0 references
    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
    0 references
    secret sharing scheme
    0 references
    information ratio
    0 references
    access structure
    0 references
    entropy
    0 references
    graph theory
    0 references
    0 references