Smallest Graphs Achieving the Stinson Bound

DOI10.1109/TIT.2020.2965102MaRDI QIDQ5124451zbMATH OpenOpenAlexFDO

Authors Máté Gyarmati, Péter Ligeti

Publication date 29 September 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.11598

zbMATH Keywords

information ratioperfect secret sharing scheme

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Authentication, digital signatures and secret sharing (94A62)

Abstract: Perfect secret sharing scheme is a method of distribute a secret information $s$ among participants such that only predefined coalitions, called qualified subsets of the participants can recover the secret, whereas any other coalitions, the unqualified subsets cannot determine anything about the secret. The most important property is the efficiency of the system, which is measured by the information ratio. It can be shown that for graphs the information ratio is at most $(delta+1)/2$ where $delta$ is the maximal degree of the graph. Blundo et al. constructed a family of $delta$-regular graphs with information ratio $(delta+1)/2$ on at least $ccdot{6}^{d}elta$ vertices. We improve this result by constructing a significantly smaller graph family on $ccdot{2}^{d}elta$ vertices achieving the same upper bound both in the worst and the average case.

Recommendations

• Smallest maximal matchings of graphs
• scientific article; zbMATH DE number 951844
• The smallest nonevasive graph property
• scientific article; zbMATH DE number 1409195
• scientific article; zbMATH DE number 4043879
• Graphs with the smallest number of minimum cut sets
• On the least size of a graph with a given degree set
• scientific article; zbMATH DE number 3843788
• On the graphs with minimum Sombor index
• The smallest strictly Neumaier graph and its generalisations

Cited in

(3)

• On the information ratio of graphs without high-degree neighbors
• The smallest strictly Neumaier graph and its generalisations
• Secret sharing on regular bipartite access structures

This page was built for publication: Smallest Graphs Achieving the Stinson Bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124451)