Minimum rank of a graph

In mathematics, the minimum rank is a graph parameter $\operatorname {mr} (G)$ 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 $G$ is denoted by $\operatorname {mr} (G)$ and is defined as the smallest rank of any generalized adjacency matrix of the graph.

Properties

• 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.

Characterization of known graph families

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

• For $n\geq 2$, the complete graph K_n 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 P_n 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 C_n on n vertices has minimum rank n − 2.
• Let $G$ be a 2-connected graph. Then $\operatorname {mr} (G)=|G|-2$ if and only if $G$ is a linear 2-tree.
• A graph $G$ has $\operatorname {mr} (G)\leq 2$ if and only if the complement of $G$ is of the form $(K_{s_{1}}\cup K_{s_{2}}\cup K_{p_{1},q_{1}}\cup \cdots \cup K_{p_{k},q_{k}})\vee K_{r}$ for appropriate nonnegative integers $k,s_{1},s_{2},p_{1},q_{1},\ldots ,p_{k},q_{k},r$ with $p_{i}+q_{i}>0$ for all $i=1,\ldots ,k$.

References

• Fallat, Shaun; Hogben, Leslie, "The minimum rank of symmetric matrices described by a graph: A survey", Linear Algebra and its Applications 426 (2007) (PDF), pp. 558–582.