In mathematics, the minimum rank is a graph parameter mr ( G ) for any graph G. It was motivated by the Colin de Verdière's invariant.
The adjacency matrix of a given undirected graph is a symmetric matrix whose rows and columns both correspond to the vertices of the graph. Its coefficients are all 0 or 1, and the coefficient in row i and column j is nonzero whenever vertex i is adjacent to vertex j in the graph. More generally, one can define a generalized adjacency matrix to be any matrix of real numbers with the same pattern of nonzeros. The minimum rank of the graph G is denoted by mr ( G ) and is defined as the smallest rank of any generalized adjacency matrix of the graph.
The minimum rank of a graph is always at most equal to n − 1, where n is the number of vertices in the graph.For every induced subgraph H of a given graph G, the minimum rank of H is at most equal to the minimum rank of G.If a given graph is not connected, then its minimum rank is the sum of the minimum ranks of its connected components.The minimum rank is a graph invariant: any two isomorphic graphs necessarily have the same minimum rank.Several families of graphs may be characterized in terms of their minimum ranks.
For n ≥ 2 , the complete graph Kn on n vertices has minimum rank one. The only graphs that are connected and have minimum rank one are the complete graphs.A path graph Pn on n vertices has minimum rank n − 1. The only n-vertex graphs with minimum rank n − 1 are the path graphs.A cycle graph Cn on n vertices has minimum rank n − 2.Let G be a 2-connected graph. Then mr ( G ) = | G | − 2 if and only if G is a linear 2-tree.A graph G has mr ( G ) ≤ 2 if and only if the complement of G is of the form ( K s 1 ∪ K s 2 ∪ K p 1 , q 1 ∪ ⋯ ∪ K p k , q k ) ∨ K r for appropriate nonnegative integers k , s 1 , s 2 , p 1 , q 1 , … , p k , q k , r with p i + q i > 0 for all i = 1 , … , k .