On the rank spread of graphs

Abstract

For a simple graph G = (𝒱, ℰ) with vertex-set 𝒱 = {1, … , n}, let 𝒮(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 mr(G) of G is the smallest possible rank over all matrices in 𝒮(G). The rank spread r v (G) of G at a vertex v, defined as mr(G) − mr(G − v), can take values ϵ ∈ {0, 1, 2}. In general, distinct vertices in a graph may assume any of the three values. For ϵ = 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 ϵ = 0, will a single matrix A in 𝒮(G) determine when a graph has uniform rank spread. Moreover, a graph G, with vertices of rank spread zero or one only, is a λ-core graph for a λ-optimal matrix A in 𝒮(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.