Hossein Hajiabolhassan ; Farokhlagha Moazami - Secure frameproof codes through biclique covers

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

Authors: Hossein Hajiabolhassan ORCID-iD1,2; Farokhlagha Moazami 3

  • 1 Department of Mathematical Sciences [Tehran]
  • 2 Institute for Research in Fundamental Science [Terhan]
  • 3 Department of Mathematics [Tehran]

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
Accepted on: June 9, 2015
Submitted on: April 10, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 2102.07486
Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.dam.2022.04.001
Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.procs.2021.11.023
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.2102.07486
  • 10.1016/j.dam.2022.04.001
  • 10.1016/j.procs.2021.11.023
  • 2102.07486
  • 10.48550/arxiv.2102.07486
Upper bounds on the Boolean rank of Kronecker products

Consultation statistics

This page has been seen 233 times.
This article's PDF has been downloaded 213 times.