Discrete Mathematics & Theoretical Computer Science, Vol 14, No 2 (2012)

Font Size:  Small  Medium  Large

Secure Frameproof Code Through Biclique Cover

Hossein Hajiabolhassan, Farokhlagha Moazami


For a binary code Γ of length v , a v -word w produces by a set of codewords {w1,…,wr} ⊆Γ if for all i=1,…,v , we have wi∈{wi1, …, wir} . We call a code r -secure frameproof of size t if |Γ|=t and for any v -word that is produced by two sets C1 and C2 of size at most r , then the intersection of these sets is non-empty. A d -biclique cover of size v of a graph G is a collection of v complete bipartite subgraphs of G such that each edge of G belongs to at least d of these complete bipartite subgraphs. In this paper, we show that for t≥2r, an r-secure frameproof code of size t and length v exists if and only if there exists a 1-biclique cover of size v for the Kneser graph KG(t,r) whose vertices are all r-subsets of a t-element set and two r-subsets are adjacent if their intersection is empty. Then we investigate some connection between the minimum size of d-biclique covers of Kneser graphs and cover-free families, where an (r,w; d) cover-free family is a family of subsets of a finite set X such that the intersection of any r members of the family contains at least d elements that are not in the union of any other w members. The minimum size of a set X for which there exists an (r,w;d) cover-free family with t blocks is denoted by N((r,w;d),t). We prove that for t > 2r and r>s, we have bcd(KG(t,r))≥bcm(KG(t,s)), where m=N((r-s,r-s;d),t-2s). Finally, we show that for any 1≤i < r, 1≤j < w, and t≥r+w we have N((r,w;d),t)≥N((r-i,w-j;m),t), where m=N((i,j;d),t-r-w+i+j).

Full Text: PDF PostScript