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
.
