MINIMUM RANK OF EDGE SUBDIVISIONS OF GRAPHS

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 x n matrices whose nonzero or-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 vertical bar A is an element of 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 (sic). 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 (sic) often depends only upon the number of vertices of G. In conclusion, some illustrative examples and open questions are presented.