Minimum rank of edge subdivisions of graphs

Abstract

Let F be a field, let G be an undirected graph on n vertices, and let S(F, G)be the set of all F-valued symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The minimum rank of G over F is defined to be mr(F, G) = min{rank A | A ∈ S(F, G)}. The problem of finding the minimum rank (maximum nullity) of edge subdivisions of a given graph G is investigated. Is is shown that if an edge is adjacent to a vertex of degree 1 or 2, its maximum nullity is unchanged upon subdividing the edge. This enables us to reduce the problem of finding the minimum rank of any graph obtained from G by subdividing edges to finding the minimum rank of those graphs obtained from G by subdividing each edge at most once. The graph obtained by subdividing each edge of G once is called its subdivision graph and is denoted by ❛G. It is shown that its maximum nullity is an upper bound for the maximum nullity of any graph obtained from G by subdividing edges. It is also shown that the minimum rank of ❛G often depends only upon the number of vertices of G. In conclusion, some illustrative examples and open questions are presented.