On the rank spread of graphs |
| |
Authors: | Irene Sciriha CM da Fonseca |
| |
Institution: | 1. Department of Mathematics, Faculty of Science , University of Malta , Msida MSD2080, Malta irene.sciriha-aquilina@um.edu.mt;3. CMUC, Department of Mathematics , University of Coimbra , 3001-454 Coimbra, Portugal |
| |
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. |
| |
Keywords: | λ–optimal matrix minimum rank maximum nullity rank spread core graph |
|
|