On the minimum vector rank of multigraphs

Lon H. Mitchell, Sivaram K. Narayan, Ian Rogers

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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.

Original languageEnglish
Pages (from-to)661-672
Number of pages12
JournalElectronic Journal of Linear Algebra
Volume20
DOIs
StatePublished - 2010

Keywords

  • Chordal graph
  • Duplicate vertices
  • Minimum semidefinite rank
  • Minimum vector rank

Fingerprint

Dive into the research topics of 'On the minimum vector rank of multigraphs'. Together they form a unique fingerprint.

Cite this