Maximum generic nullity of a graph |
| |
Authors: | Leslie Hogben Bryan Shader |
| |
Affiliation: | a Department of Mathematics, Iowa State University, Ames, IA 50011, USA b American Institute of Mathematics, 360 Portage Ave., Palo Alto, CA 94306, USA c Department of Mathematics, University of Wyoming, Laramie, WY 82071, USA |
| |
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. |
| |
Keywords: | 05C50 15A03 15A18 |
本文献已被 ScienceDirect 等数据库收录! |
|