On Strong Biclique Covering

Abstract

A \( t \)-strong biclique covering of a graph \( G \) is an edge covering \(
E(G) = \bigcup_{i=1}^{t} E(H_i)\) where each \( H_i \) is a set of disjoint bicliques; say \( H_{i,1}, …, H_{i,r_i} \), such that the graph \( G \) has no edge between \( H_{i,k} \) and \( H_{i,j} \) for any \( 1 \leq j < k \leq r_i \). The strong biclique covering index \( S(G) \) is the minimum number \( t \) for which there exists a \( t \)-strong biclique covering of \( G \). In this paper, we study the strong biclique covering index of graphs. The strong biclique covering index of graphs was introduced in [H. Hajiabolhassan, A. Cheraghi, Bounds for Visual Cryptography Scheme, Discrete Applied Mathematics, 158 (2010), 659-665] to study the pixel expansion of visual cryptology. We present a lower bound for the strong biclique covering index of graphs and also we introduce upper bounds for different products of graphs.