Title of article :
Biclique comparability digraphs of bipartite graphs and minimum ranks of partial matrices
Author/Authors :
Terry A. McKee، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2004
Pages :
6
From page :
165
To page :
170
Abstract :
t Every bipartite graph has a biclique comparability digraph whose vertices are the inclusion-maximal complete bipartite subgraphs of the bipartite graph and whose arcs correspond to inclusions of the relevant color classes. I characterize those digraphs that correspond to bipartite graphs and, in particular, those that correspond to chordal bipartite graphs. This is motivated by work on finding the minimum rank of completions of partially specified matrices. In particular, Woerdeman (Integral Equations Operator Theory 10 (1987) 859) proved a formula for minimum rank in special cases that can be naturally reformulated in terms of the biclique comparability digraphs of the bipartite graphs that have the partial matrices as incidence matrices. Cohen et al. (Oper. Theory Adv. Appl. 40 (1989) 165) conjecture that this formula actually gives the minimum rank if and only if the corresponding bipartite
Keywords :
Comparability graphs , Bipartite graphs , Chordal bipartite graphs , Minimum ranks , Partial matrices
Journal title :
Discrete Mathematics
Serial Year :
2004
Journal title :
Discrete Mathematics
Record number :
948622
Link To Document :
بازگشت