On the Minimum Vector Rank of Multigraphs

Authors

Lon Mitchell, University of South Florida St. PetersburgFollow
Sivaram Narayan
Ian Rogers

SelectedWorks Author Profiles:

Lon Mitchell

Document Type

Article

Publication Date

2010

ISSN

1081-3810

Abstract

The minimum vector rank (mvr) of a graph over a field F is the smallest d for which a faithful vector representation of G exists in Fd. For simple graphs, minimum semidefinite rank (msr) and minimum vector rank differ by exactly the number of isolated vertices. We explore the relationship between msr and mvr for multigraphs and show that a result linking the msr of chordal graphs to clique cover number also holds for the mvr of multigraphs. We study the difference between msr and mvr in the removal of duplicate vertices in multigraphs, and relate mvr to certain coloring problems.

Publisher

International Linear Algebra Society

Recommended Citation

Mitchell, L., Narayan, S. & Rogers, I. (2010). On the minimum vector rank of multigraphs. Electronic Journal of Linear Algebra, 20, 661-672. https://doi.org/10.13001/1081-3810.1400.