Maximal graphs with respect to rank

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. A reduced graph G is said to be maximal if any reduced graph containing G as a proper induced subgraph has a higher rank. The main intent of this paper is to present some results on maximal graphs. First, we introduce a characterization of maximal trees (a reduced tree is a maximal tree if it is not a proper subtree of a reduced tree with the same rank). Next, we give a near-complete characterization of maximal ‘generalized friendship graphs.’ Finally, we present an enumeration of all maximal graphs with ranks 8 and 9. The ranks up to 7 were already done by Lepovic (1990), Ellingham (1993), and Lazic (2010).