• PDF
• Cite
• Share
Article Contents  Article Contents

# Optimal information ratio of secret sharing schemes on Dutch windmill graphs

• * Corresponding author: Bagher Bagherpour
• One of the basic problems in secret sharing is to determine the exact values of the information ratio of the access structures. This task is important from the practical point of view, since the security of any system degrades as the amount of secret information increases.

A Dutch windmill graph consists of the edge-disjoint cycles such that all of them meet in one vertex. In this paper, we determine the exact information ratio of secret sharing schemes on the Dutch windmill graphs. Furthermore, we determine the exact ratio of some related graph families.

Mathematics Subject Classification: Primary: 94A60, 94A62.

 Citation: • • Figure 1.  The Dutch windmill graph $D_4^{(k)}$ with predefined labelling

Figure 2.  The friendship graph $F_k$ with predefined labelling

Table 1.  Subgraphs of the graph $C(\mathcal{F}_k)$

 $G$ $V$ $S_1(V)$ $\{v_c, v^{1}_2, v^{1}_{n_1}, \ldots, v^{k}_{2}, v^{k}_{n_k}\}$ $\Pi_1 =\{(2k-1) \times S_{1}(V)\}$ $S^{i}_{1}(V)$$i\in \{1, \ldots, k\} \{v_c, v^{i}_2, v^{i}_{3}\} \Pi_2 =\{1 \times S^{i}_1(V): i\in \{1, \ldots, k\}\} S^{i}_{2}(V)$$i\in \{1, \ldots, k\}$ $\{v_c, v^{i}_{n_i}, v^{i}_{n_i-1}\}$ $\Pi_3 =\{1 \times S^{i}_{2}(V): i\in \{1, \ldots, k\}\}$ $P^{i}_1(V)$$i\in \{1, \ldots, k\} \{v^{i}_2, v^{i}_3, \ldots, v^{i}_{n_i}\} \Pi_4 =\{(2k-1) \times P^{i}_1(V): i \in \{1, \ldots, k\}\} P^{i}_2(V)$$i\in \{1, \ldots, k\}$ $\{v^{i}_3, v^{i}_{4}, \ldots, v^{i}_{n_i-1}\}$ $\Pi_5 =\{1 \times P^{i}_2(V): i \in \{1, \ldots, k\}\}$

Table 2.  Subgraphs of the graph $C'(\mathcal{F}_k)$

 $G$ $V$ $S_1(V)$ $\{v_c, v', v^{1}_2, v^{1}_{n_1}, \ldots, v^{k}_{2}, v^{k}_{n_k}\}$ $\Pi_1 =\{(2k) \times S_{1}(V)\}$ $S^{i}_{1}(V)$$i\in \{1, \ldots, k\} \{v_c, v^{i}_2, v^{i}_{3}\} \Pi_2 =\{1 \times S^{i}_1(V): i\in \{1, \ldots, k\}\} S^{i}_{2}(V)$$i\in \{1, \ldots, k\}$ $\{v_c, v^{i}_{n_i}, v^{i}_{n_i-1}\}$ $\Pi_3 =\{1 \times S^{i}_{2}(V): i\in \{1, \ldots, k\}\}$ $S'(V)$ $\{v_c, v' \}$ $\Pi_4 =\{1 \times S'(V) \}$ $P^{i}_1(V)$$i\in \{1, \ldots, k\} \{v^{i}_2, v^{i}_3, \ldots, v^{i}_{n_i}\} \Pi_5 =\{2k \times P^{i}_1(V): i \in \{1, \ldots, k\}\} P^{i}_2(V)$$i\in \{1, \ldots, k\}$ $\{v^{i}_3, v^{i}_{4}, \ldots, v^{i}_{n_i-1}\}$ $\Pi_6 =\{1 \times P^{i}_2(V): i \in \{1, \ldots, k\}\}$

Table 3.  Subgraphs of the graph $D^{(k)}_{4}$

 $G$ $V(G)$ $E(G)$ $G_1$ $\{v_c, v_1, v_3, \ldots, v_{3k-2}, v_{3k}\}$ $\{v_c v_j , v_c v_{j+2}:$ $j \in \{1, 4, \ldots, 3k-2 \}\}$ $G_{1+(i+2)/3}$$i\in \{1, 4, \ldots 3k-2 \} \{v_c, v_i, v_{i+1}, v_{i+2}\} \{ v_c v_i, v_c v_{i+2}, v_i v_{i+1}, v_{i+1} v_{i+2}\} G_{k+1+(i+2)/3}$$i\in \{1, 4, \ldots, 3k-2 \}$ $\{v_i, v_{i+1}, v_{i+2}\}$ $\{ v_i v_{i+1}, v_{i+1} v_{i+2}\}$

Table 4.  Subgraphs of the graph $D'^{(k)}_{4}$

 $G$ $V(G)$ $E(G)$ $G_1$ $\{v_c, v_1, v_3, \ldots, v_{3k-2}, v_{3k},$ $v'\}$ $\{v_c v_j , v_c v_{j+2}, v_c v': j\in\{1, 4,$ $\ldots, 3k-2\}\}$ $G_{1+(i+2)/3}$$i\in \{1, 4, \ldots 3k-2 \} \{v_c, v_i, v_{i+1}, v_{i+2}\} \{ v_c v_i, v_c v_{i+2}, v_i v_{i+1}, v_{i+1} v_{i+2}\} G_{k+2} \{v_c, v' \} \{v_c v' \} G_{k+2+(i+2)/3}$$i\in \{1, 4, \ldots, 3k-2 \}$ $\{v_i, v_{i+1}, v_{i+2}\}$ $\{ v_i v_{i+1}, v_{i+1} v_{i+2}\}$

Table 5.  Subgraphs of the graph $v\nabla \mathcal{F}_k$

 $G$ $V(G)$ $E(G)$ $G_1$ $\{v, V(H_1), V(H_2),$ $\ldots, V(H_k)\}$ $\{v w: w \in \{ V(H_1), \ldots, V(H_k)\}\}$ $G_{1+i}$$i\in \{1, \ldots, k\} \{v, V(H_i)\} \{ E(H_i), v w:w \in V(H_i) \} G_{k+1+i}$$i\in \{1, \cdots, k \}$ $V(H_i)$ $E(H_i)$

Table 6.  Subgraphs of the graph $v\nabla \mathcal{F'}_k$

 $G$ $V(G)$ $E(G)$ $G_1$ $\{v, V(H_1), \ldots, V(H_k), v'\}$ $\{v v', v w: w \in \{ V(H_1), \ldots, V(H_k) \}$ $G_{1+i}$$i\in \{1, \ldots, k\} \{v, V(H_i)\} \{ E(H_i), v w:w \in V(H_i) \} G_{k+2} \{v, v'\} \{v v' \} G_{k+2+i}$$i\in \{1, \cdots, k \}$ $V(H_i)$ $E(H_i)$
• Figures(2)

Tables(6)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint