pith. sign in

arxiv: 1301.4790 · v1 · pith:LY4COP4Mnew · submitted 2013-01-21 · 🧮 math.CO

On the Biclique cover of the complete graph

classification 🧮 math.CO
keywords coverbicliquecompletegraphtypebicliquesbipartitebound
0
0 comments X
read the original abstract

Let $K$ be a set of $k$ positive integers. A biclique cover of type $K$ of a graph $G$ is a collection of complete bipartite subgraphs of $G$ such that for every edge $e$ of $G$, the number of bicliques need to cover $e$ is a member of $K$. If $K=\{1,2,..., k\}$ then the maximum number of the vertices of a complete graph that admits a biclique cover of type $K$ with $d$ bicliques, $n(k,d)$, is the maximum possible cardinality of a $k$-neighborly family of standard boxes in $\mathbb{R}^d$. In this paper, we obtain an upper bound for $n(k,d)$. Also, we show that the upper bound can be improved in some special cases. Moreover, we show that the existence of the biclique cover of type $K$ of the complete bipartite graph with a perfect matching removed is equivalent to the existence of a cross $K$-intersection family.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.