On the information ratio of graphs with many leaves

Year, pages: 2019, 97 - 108

We investigate the information ratio of graph-based secret sharing schemes. This ratio characterizes the efficiency of a scheme measured by the amount of information the participants must remember for each bits in the secret. We examine the information ratio of several systems based on graphs with many leaves, by proving non-trivial lower and upper bounds for the ratio. On one hand, we apply the so-called entropy method for proving that the lower bound for the information ratio of $n$-sunlet graphs composed of a 1-factor between the vertices of a cycle $C_n$ and $n$ independent vertices is 2. On the other hand, some symmetric and recursive constructions are given that yield the upper bounds. In particular, we show that the information ratio of every graph composed of a 1-factor between a complete graph $K_n$ and at most 4 independent vertices is smaller than 2.

Gyarmati, M., Ligeti, P. 2019. On the information ratio of graphs with many leaves. In Tatra Mountains Mathematical Publications, vol. 73, no.1, pp. 97-108. 1210-3195. DOI: https://doi.org/10.2478/tmmp-2019-0008

Gyarmati, M., Ligeti, P. (2019). On the information ratio of graphs with many leaves. Tatra Mountains Mathematical Publications, 73(1), 97-108. 1210-3195. DOI: https://doi.org/10.2478/tmmp-2019-0008

Publisher: Mathematical Institute, Slovak Academy of Sciences, Bratislava

© 2019 Mathematical Institute, Slovak Academy of Sciences. Licensed under the Creative Commons Attribution-NC-ND 4.0 International Public License.