Minimum rank of a graph


In mathematics, the minimum rank is a graph parameter for any graph G. It was motivated by the Colin de Verdière's invariant.

Definition

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 is denoted by and is defined as the smallest rank of any generalized adjacency matrix of the graph.

Properties

Several families of graphs may be characterized in terms of their minimum ranks.