Structural properties of biclique graphs and the distance formula

A $\mathit{\text{biclique}}$ is a maximal induced complete bipartite subgraph of $G$. The $\mathit{\text{biclique}}\mathit{\text{graph}}$ of a graph $G$, denoted by $KB(G)$, is the intersection graph of the family of all bicliques of $G$. In this work we study some structural properties of biclique graphs which are necessary conditions for a graph to be a biclique graph. In particular, we prove that for biclique graphs that are neither a $K_3$ nor a $\mathit{\text{diamond}}$, the number of vertices of degree $2$ is less than half the number of vertices in the graph. Also, we present forbidden structures. For this, we introduce a natural definition of the distance between bicliques in a graph. We give a formula that relates the distance between bicliques in a graph $G$ and the distance between their respective vertices in $KB(G)$. Using these results, we can prove not only this new necessary condition involving the degree, but also that some graphs are not biclique graphs. For example, we show that the $\mathit{\text{crown}}$ is the smallest graph that is not a biclique graph although the known necessary condition for biclique graphs holds, answering an open problem about biclique graphs. Finally, we present some interesting related conjectures and open problems.