In this paper we continue a study of secret sharing schemes for access
structures based on graphs. Given a graph G, we require that a subset
of participants can compute a secret key if they contain an edge of G
; otherwise, they can obtain no information regarding the key. We stud
y the information rate of such schemes, which measures how much inform
ation in being distributed as shares compared with the size of the sec
ret key, and the average information rate, which is the ratio between
the secret size and the arithmetic mean of the size of the shares. We
give both upper and lower bounds on the optimal information rate and a
verage information rate that can be obtained. Upper bounds arise by ap
plying entropy arguments due to Capocelli et al. [15]. Lower bounds co
me from constructions that are based on graph decompositions. Applicat
ion of these constructions requires solving a particular linear progra
mming problem. We prove some general results concerning the informatio
n rate and average information rate for paths, cycles, and trees. Also
, we study the 30 (connected) graphs on at most five vertices, obtaini
ng exact values for the optimal information rate in 26 of the 30 cases
, and for the optimal average information rate in 28 of the 30 cases.