Visual Cryptography Scheme for the Mindom Access Structure of a Graph

Abstract

Let $G=(V,E)$ be a connected graph with domination number $\gamma \ge 2$. In this paper, we discuss the construction of a visual cryptography scheme for the mindom access structure ${\mathrm{\Gamma }}_D(G)$ with a basis consisting of all $\gamma$-sets of $G$. We prove that the access structure ${\mathrm{\Gamma }}_D(G)$ is a $(2,n)$-threshold access structure if and only if $n$ is even and $G=K_n–M$, where $M$ is a perfect matching in $K_n$. Further, the $(k,n)$-VCS with $k<n$ can be realized as a ${\mathrm{\Gamma }}_D(G)$-VCS if and only if $k=2$ and $n$ is even. We also construct ${\mathrm{\Gamma }}_D(G)$-VCS for several classes of graphs such as complete bipartite graphs, cycles $C_n$, and $K_n–C_n$, and we have achieved substantial reduction in the pixel expansion when compared to the VCS constructed by using other known methods.