Secure Frameproof Code Through Biclique Cover

Abstract: For a binary code

G a m m a

of length

v

, a

v

-word

w

produces by a set of codewords

w^{1}, ..., w^{r} s u b s e t e q G a m m a

if for all

i = 1, ..., v

, we have

w_{i} i n w_{i}^{1}, ..., w_{i}^{r}

. We call a code

r

-secure frameproof of size

t

if

| G a m m a | = t

and for any

v

-word that is produced by two sets

C_{1}

and

C_{2}

of size at most

r

then the intersection of these sets is nonempty. 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 g e q 2 r

, 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

m K G (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 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. Also, we present an upper bound for 1-biclique covering number of Kneser graphs.

Recommendations

Cited in

(5)

This page was built for publication: Secure Frameproof Code Through Biclique Cover