Vol. 7, No. 5, 2014

Download this article
Download this article For screen
For printing
Recent Issues

Volume 12
Issue 2, 181–360
Issue 1, 1–180

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the Journal
Subscriptions
Editorial Board
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
Computing positive semidefinite minimum rank for small graphs

Steven Osborne and Nathan Warnberg

Vol. 7 (2014), No. 5, 595–609
Abstract

The positive semidefinite minimum rank of a simple graph G is defined to be the smallest possible rank over all positive semidefinite real symmetric matrices whose ij-th entry (for ij) is nonzero whenever {i,j} is an edge in G and is zero otherwise. The computation of this parameter directly is difficult. However, there are a number of known bounding parameters and techniques which can be calculated and performed on a computer. We programmed an implementation of these bounds and techniques in the open-source mathematical software Sage. The program, in conjunction with the orthogonal representation method, establishes the positive semidefinite minimum rank for all graphs of order 7 or less.

Keywords
zero forcing number, maximum nullity, minimum rank, positive semidefinite, zero forcing, graph, matrix
Mathematical Subject Classification 2010
Primary: 05C50
Secondary: 15A03
Milestones
Received: 19 July 2011
Revised: 13 December 2011
Accepted: 12 December 2013
Published: 1 August 2014

Communicated by Chi-Kwong Li
Authors
Steven Osborne
Department of Mathematics
Iowa State University
Ames, IA 50011
United States
Nathan Warnberg
Department of Mathematics
Iowa State University
Ames, IA 50011
United States