Facebook Instagram Twitter RSS Feed PodBean Back to top on side

On the information ratio of graphs with many leaves

In: Tatra Mountains Mathematical Publications, vol. 73, no. 1
Máté Gyarmati - Péter Ligeti
Detaily:
Rok, strany: 2019, 97 - 108
Jazyk: eng
Kľúčové slová:
secret sharing, information ratio, entropy method
Typ článku: scientific article/mathematics
Typ dokumentu: pdf
O článku:
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 $Cn$ 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 $Kn$ and at most 4 independent vertices is smaller than 2.
Ako citovať:
ISO 690:
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

APA:
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
O vydaní:
Vydavateľ: Mathematical Institute, Slovak Academy of Sciences, Bratislava
Publikované: 15. 8. 2019
Verejná licencia:
© 2019 Mathematical Institute, Slovak Academy of Sciences. Licensed under the Creative Commons Attribution-NC-ND 4.0 International Public License.