Biclique Covers and Partitions of Unipathic Digraphs
Kim A.S. Hefner, J. Richard Lundgren, John S. Maybee · 2017
A digraph D is strongly unipathic if it has exactly one directed path from any vertex to any other. We show that the only bicliques in such a digraph are claws, and so it follows that the claw cover, biclique cover and biclique partition numbers of D are all equal. Equivalently, the term, Boolean and nonnegative integer ranks of its adjacency matrix A ( D ) are all equal. We extend the unipathic property to sets of vertex disjoint paths, and prove that the above ranks are all equal to the ordinary real rank of A ( D ) . Also, in the course of the paper, we survey a number of useful characterizations of directed versions of the clique covering and partition numbers that recur in Pullman&s;s work.