Minimum Rank, Maximum Nullity, and Zero Forcing Number of Graphs

Simple item page
dc.contributor.author Fallat, Shaun
dc.contributor.author Hogben, Leslie
dc.contributor.author Hogben, Leslie
dc.contributor.department Electrical and Computer Engineering
dc.contributor.department Mathematics
dc.date 2019-07-13T14:07:34.000
dc.date.accessioned 2020-06-30T06:00:26Z
dc.date.available 2020-06-30T06:00:26Z
dc.date.copyright Wed Jan 01 00:00:00 UTC 2014
dc.date.issued 2014-01-01
dc.description.abstract <p>This chapter represents an overview of research related to a notion of the “<em>rank of a graph</em>" and the dual concept known as the “<em>nullity of a graph</em>," from the point of view of associating a fixed collection of symmetric or Hermitian matrices to a given graph. This topic and related questions have enjoyed a fairly large history within discrete mathematics, and have become very popular among linear algebraists recently, partly based on its connection to certain inverse eigenvalue problems, but also because of the many interesting applications (e.g., to communication complexity in computer science and to control of quantum systems in mathematical physics) and implications to several facets of graph theory.</p> <p>This chapter is divided into eight parts, beginning in Section 1 with what we feel is the standard minimum rank problem concerning symmetric matrices over the real numbers associated with a simple graph. We continue with important variants of the standard minimum rank problem and related parameters, including the concept of minimum rank over other fields (Section 2), the positive semidefinite minimum rank of a graph (Section 3), graph coloring parameters known as <em>zero forcing numbers</em> (Section 4) and the more classical and celebrated parameters due to Y. Colin de Verdière (Section 5). Section 6 contains more advanced topics relevant to the previous five sections, and Section 7 discusses two well-known conjectures related to minimum rank. Whereas the first seven sections concern primarily symmetric matrices and the diagonal of the matrix is free, in Section 8 we discuss minimum rank problems with no symmetry assumption but the diagonal constrained.</p> <p>NB: The topics discussed in this chapter are in an active research area and the facts presented here represent the state of knowledge as of the writing of this chapter in 2012.</p>
dc.description.comments <p>This is an Accepted Manuscript of the book chapter Fallat, Shaun M., and Leslie Hogben. "Minimum Rank, Maximum Nullity, and Zero Forcing Number of Graphs." In <em>Handbook of Linear Algebra</em>, Second Edition, edited by Leslie Hogben. Boca Raton, Florida : CRC Press/Taylor & Francis Group, 2014: 46-1 to 46-36. Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/math_pubs/212/
dc.identifier.articleid 1218
dc.identifier.contextkey 14584233
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/212
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/54604
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/math_pubs/212/2014_HogbenLeslie_MinimumRankMaximum.pdf|||Fri Jan 14 22:35:37 UTC 2022
dc.subject.disciplines Algebra
dc.subject.disciplines Applied Mathematics
dc.subject.disciplines Discrete Mathematics and Combinatorics
dc.title Minimum Rank, Maximum Nullity, and Zero Forcing Number of Graphs
dc.type article
dc.type.genre book_chapter
dspace.entity.type Publication
relation.isAuthorOfPublication 0131698a-00df-41ad-8919-35fb630b282b
relation.isOrgUnitOfPublication a75a044c-d11e-44cd-af4f-dab1d83339ff
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
File
Original bundle
Now showing 1 - 1 of 1
Name:
2014_HogbenLeslie_MinimumRankMaximum.pdf
Size:
615.77 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Publications