Linearly Independent Vertices and Minimum Semidefinite Rank

Authors

Philip Hackney
Benjamin Harris
Margaret Lay
Lon Mitchell, University of South Florida St. PetersburgFollow
Sivaram Narayan
Amanda Pascoe

SelectedWorks Author Profiles:

Lon Mitchell

Document Type

Article

Publication Date

2009

ISSN

0024-3795

Abstract

We study the minimum semidefinite rank of a graph using vector representations of the graph and of certain subgraphs. We present a sufficient condition for when the vectors corresponding to a set of vertices of a graph must be linearly independent in any vector representation of that graph, and conjecture that the resulting graph invariant is equal to minimum semidefinite rank. Rotation of vector representations by a unitary matrix allows us to find the minimum semidefinite rank of the join of two graphs. We also improve upon previous results concerning the effect on minimum semidefinite rank of the removal of a vertex.

Publisher

Elsevier

Recommended Citation

Hackney, P., Harris, B., Lay, M., Mitchell, L., Narayan, S., & Pascoe, A. (2009). Linearly independent vertices and minimum semidefinite rank. Linear Algebra and its Applications, 431(8), 1105-1115. https://doi.org/10.1016/j.laa.2009.03.030.