Ranks of Trees and Grid Graphs

Abstract

There has been a great deal of interest in relating the rank of the adjacency matrix of a graph to other fundamental numbers associated with a graph. We present two results which may be helpful in guiding further development in this area. Firstly, we give a linear time algorithm for finding the rank of any tree which is twice its edge independence number. Secondly, we give a formula for the rank of any grid graph consisting of $mn$ vertices arranged in a rectangular grid of $m$ rows and $n$ columns on a planar, cylindrical, or toroidal surface.