Campus Units

Mathematics

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

2-2010

Journal or Book Title

Linear Algebra and its Applications

Volume

432

First Page

857

Last Page

866

DOI

10.1016/j.laa.2009.09.025

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.

Comments

This is a manuscript of an article from Linear Algebra and its Applications 432 (2010): 857, doi:10.1016/j.laa.2009.09.025. Posted with permission.

Rights

This manuscript version is made available under the CCBY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/

Copyright Owner

Elsevier Inc.

Language

en

File Format

application/pdf

Published Version

Share

COinS