Maximum Generic Nullity of a Graph

Date
2010-02-01
Authors
Hogben, Leslie
Shader, Bryan
Hogben, Leslie
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that maximum generic nullity is bounded above by edge connectivity and below by vertex connectivity. Results on random graphs are used to show that as n goes to infinity almost all graphs have equal maximum generic nullity, vertex connectivity, edge connectivity, and minimum degree.

Description
<p>This is a manuscript of an article from <em>Linear Algebra and its Applications </em>432 (2010): 857, doi:<a href="http://dx.doi.org/10.1016/j.laa.2009.09.025" target="_blank">10.1016/j.laa.2009.09.025</a>. Posted with permission.</p>
Keywords
Minimum rank, Maximum nullity, Maximum corank, Maximum generic nullity, Graph, Rank, Nullity, Corank, Symmetric matrix, Orthogonal representation
Citation
Collections