Ranks of Trees and Grid Graphs

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.