Vol. 7, No. 5, 2014

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

Volume 11, 1 issue

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
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
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