## Abstract

The minimum semidefinite rank (msr) of a graph is the minimum rank among positive semidefinite matrices with the given graph. The OS-number is a useful lower bound for msr, which arises by considering ordered vertex sets with some connectivity properties. In this paper, we develop two new interpretations of the OS-number. We first show that OS-number is also equal to the maximum number of vertices which can be orthogonally removed from a graph under certain nondegeneracy conditions. Our second interpretation of the OS-number is as the maximum possible rank of chordal supergraphs who exhibit a notion of connectivity we call isolation-preserving. These interpretations not only give insight into the OS-number, but also allow us to prove some new results. For example we show that msr(G) = G - 2 if and only if OS(G) = Gzsfnc - 2.

Original language | English |
---|---|

Pages (from-to) | 525-536 |

Number of pages | 12 |

Journal | Linear Algebra and Its Applications |

Volume | 436 |

Issue number | 3 |

DOIs | |

State | Published - Feb 1 2012 |

## Keywords

- Linearly independent vertices
- Minimum semidefinite rank
- Orthogonal vertex removal