Maximum Generic Nullity of a Graph

dc.contributor.author Hogben, Leslie
dc.contributor.author Shader, Bryan
dc.contributor.author Hogben, Leslie
dc.contributor.department Mathematics
dc.date 2018-02-18T06:08:02.000
dc.date.accessioned 2020-06-30T06:01:01Z
dc.date.available 2020-06-30T06:01:01Z
dc.date.copyright Fri Jan 01 00:00:00 UTC 2010
dc.date.issued 2010-02-01
dc.description.abstract <p>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.</p>
dc.description.comments <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>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/math_pubs/88/
dc.identifier.articleid 1079
dc.identifier.contextkey 9889696
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/88
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/54687
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/math_pubs/88/2010_Hogben_MaximumGeneric.pdf|||Sat Jan 15 02:17:08 UTC 2022
dc.source.uri 10.1016/j.laa.2009.09.025
dc.subject.disciplines Algebra
dc.subject.disciplines Discrete Mathematics and Combinatorics
dc.subject.keywords Minimum rank
dc.subject.keywords Maximum nullity
dc.subject.keywords Maximum corank
dc.subject.keywords Maximum generic nullity
dc.subject.keywords Graph
dc.subject.keywords Rank
dc.subject.keywords Nullity
dc.subject.keywords Corank
dc.subject.keywords Symmetric matrix
dc.subject.keywords Orthogonal representation
dc.title Maximum Generic Nullity of a Graph
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication 0131698a-00df-41ad-8919-35fb630b282b
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
File
Original bundle
Now showing 1 - 1 of 1
Name:
2010_Hogben_MaximumGeneric.pdf
Size:
260.99 KB
Format:
Adobe Portable Document Format
Description:
Collections