Minimum rank of a graph

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

DefinitionEdit

The adjacency matrix of an undirected graph is a symmetric matrix whose rows and columns both correspond to the vertices of the graph. Its elements are all 0 or 1, and the element in row i and column j is nonzero whenever vertex i is adjacent to vertex j in the graph. More generally, a generalized adjacency matrix is any symmetric matrix of real numbers with the same pattern of nonzeros off the diagonal (the diagonal elements may be any real numbers). The minimum rank of   is defined as the smallest rank of any generalized adjacency matrix of the graph; it is denoted by  .

PropertiesEdit

Here are some elementary 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.[1]
  • 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.[2]
  • If a graph is disconnected, then its minimum rank is the sum of the minimum ranks of its connected components.[3]
  • The minimum rank is a graph invariant: isomorphic graphs necessarily have the same minimum rank.

Characterization of known graph familiesEdit

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

  • For  , 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.[4]
  • 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.[5]
  • A cycle graph Cn on n vertices has minimum rank n − 2.[6]
  • Let   be a 2-connected graph. Then   if and only if   is a linear 2-tree.[7]
  • A graph   has   if and only if the complement of   is of the form   for appropriate nonnegative integers   with   for all  .[8]

NotesEdit

  1. ^ Fallat–Hogben, Observation 1.2.
  2. ^ Fallat–Hogben, Observation 1.6.
  3. ^ Fallat–Hogben, Observation 1.6.
  4. ^ Fallat–Hogben, Observation 1.2.
  5. ^ Fallat–Hogben, Corollary 1.5.
  6. ^ Fallat–Hogben, Observation 1.6.
  7. ^ Fallat–Hogben, Theorem 2.10.
  8. ^ Fallat–Hogben, Theorem 2.9.

ReferencesEdit

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