06019055

j

06019055 Sciriha, Irene da Fonseca, C.M. On the rank spread of graphs. Linear Multilinear Algebra 60, No. 1, 73-92 (2012). 2012 Taylor \& Francis, Abingdon EN $\lambda $-optimal matrix minimum rank maximum nullity rank spread core graph

doi:10.1080/03081087.2011.567389

Summary: For a simple graph $G=({\Cal V},{\Cal E})$ with vertex-set ${\Cal V}= \{1,\dots,n\}$, let ${\Cal S}(G)$ be the set of all real symmetric $n$-by-$n$ matrices whose graph is $G$. We present terminology linking established as well as new results related to the minimum rank problem, with spectral properties in graph theory. The minimum rank $\text{mr}(G)$ of $G$ is the smallest possible rank over all matrices in ${\Cal S}(G)$. The rank spread $r_v(G)$ of $G$ at a vertex $v$, defined as $\text{mr}(G)- \text{mr}(G-v)$, can take values $\varepsilon\in\{0, 1,2\}$. In general, distinct vertices in a graph may assume any of the three values. For $\varepsilon=0$ or $1$, there exist graphs with uniform $r_v(G)$ (equal to the same integer at each vertex $v$). We show that only for $\varepsilon=0$, will a single matrix ${\bold A}$ in ${\Cal S}(G)$ determine when a graph has uniform rank spread. Moreover, a graph $G$, with vertices of rank spread zero or one only, is a $\lambda$-core graph for a $\lambda$-optimal matrix ${\bold A}$ in ${\Cal S}(G)$. We also develop sufficient conditions for a vertex of rank spread zero or two and a necessary condition for a vertex of rank spread two.