Bipartite dimension

In the mathematical fields of graph theory and combinatorial optimization, the bipartite dimension or biclique cover number of a graph G = (V, E) is the minimum number of bicliques (that is complete bipartite subgraphs), needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes biclique cover. The bipartite dimension of G is often denoted by the symbol d(G). An example for a biclique edge cover is given in the following diagrams: Image:Bipartite-dimension-bipartite-graph.svg|A bipartite graph... Image:Bipartite-dimension-biclique-cover.svg|...and a covering with four bicliques Image:Bipartite-dimension-red-biclique.svg|the red biclique from the cover Image:Bipartite-dimension-blue-biclique.svg|the blue biclique from the cover Image:Bipartite-dimension-green-biclique.svg|the green biclique from the cover Image:Bipartite-dimension-black-biclique.svg|the black biclique from the cover The bipartite dimension of the n-vertex complete graph, is . The bipartite dimension of a 2n-vertex crown graph equals , where is the inverse function of the central binomial coefficient . The bipartite dimension of the lattice graph is if is even and for some integers ; and is otherwise . determine the bipartite dimension for some special graphs. For example, the path has and the cycle has . The computational task of determining the bipartite dimension for a given graph G is an optimization problem. The decision problem for bipartite dimension can be phrased as: INSTANCE: A graph and a positive integer . QUESTION: Does G admit a biclique edge cover containing at most bicliques? This problem appears as problem GT18 in Garey and Johnson's classical book on NP-completeness, and is a rather straightforward reformulation of another decision problem on families of finite sets. The set basis problem appears as problem SP7 in Garey and Johnson's book. Here, for a family of subsets of a finite set , a set basis for is another family of subsets of , such that every set can be described as the union of some basis elements from .