Fractional biclique covers and partitions of graphs

Valerie L. Watts

The electronic journal of combinatorics, Tome 13 (2006)

Résumé

A biclique is a complete bipartite subgraph of a graph. This paper investigates the fractional biclique cover number, $bc^*(G)$, and the fractional biclique partition number, $bp^*(G)$, of a graph $G$. It is observed that $bc^*(G)$ and $bp^*(G)$ provide lower bounds on the biclique cover and partition numbers respectively, and conditions for equality are given. It is also shown that $bc^*(G)$ is a better lower bound on the Boolean rank of a binary matrix than the maximum number of isolated ones of the matrix. In addition, it is noted that $bc^*(G) \leq bp^*(G) \leq \beta^*(G)$, the fractional vertex cover number. Finally, the application of $bc^*(G)$ and $bp^*(G)$ to two different weak products is discussed.

Détail

DOI : 10.37236/1100

Classification : 05C70
Mots-clés : Boolean rank, weak product