## Hajiabolhassan, Hossein and Moazami, Farokhlagha - Secure frameproof codes through biclique covers

dmtcs:585 - Discrete Mathematics & Theoretical Computer Science, December 4, 2012, Vol. 14 no. 2
Secure frameproof codes through biclique covers

Authors: Hajiabolhassan, Hossein and Moazami, Farokhlagha

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∈{w1i,...,wri} . 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 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≥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 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.

Volume: Vol. 14 no. 2
Section: Graph Theory
Published on: December 4, 2012
Submitted on: April 10, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
{"ft_lang_label":"__label__en","ft_lang_prob":0.91518503,"math_prob":0.9206284,"size":1212,"snap":"2020-34-2020-40","text_gpt3_token_len":325,"char_repetition_ratio":0.119205296,"word_repetition_ratio":0.0,"special_character_ratio":0.23927392,"punctuation_ratio":0.10714286,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9684762,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-09-22T02:19:14Z\",\"WARC-Record-ID\":\"<urn:uuid:879aa872-5d1b-44f9-976b-d2d6bd1c956f>\",\"Content-Length\":\"35730\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:f539fff6-285b-48a6-af15-b872c724f007>\",\"WARC-Concurrent-To\":\"<urn:uuid:91f09250-a272-452a-886f-67be747a9bae>\",\"WARC-IP-Address\":\"193.48.96.94\",\"WARC-Target-URI\":\"https://dmtcs.episciences.org/585\",\"WARC-Payload-Digest\":\"sha1:4NU4JU7DAEDU42F2NWE5HGB6CDD57OHR\",\"WARC-Block-Digest\":\"sha1:LBID4BDBMVC65KSM3ZKOJIP5G67AE2QL\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-40/CC-MAIN-2020-40_segments_1600400202686.56_warc_CC-MAIN-20200922000730-20200922030730-00611.warc.gz\"}"}