Rank (graph theory)

In graph theory, a branch of mathematics, the rank of an undirected graph is defined as the number n − c, where n is the number of vertices and c is the number of connected components of the graph.[1] Equivalently, the rank of a graph is the rank of the oriented incidence matrix associated with the graph.[2]

Analogously, the nullity of an undirected graph is the nullity of its incidence matrix, given by the formula m − n + c, where n and c are as above and m is the number of edges in the graph. The nullity is equal to the first Betti number of the graph. The sum of the rank and the nullity is the number of edges.

See also

Notes

  1. ↑ Weisstein, Eric W. "Graph Rank." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GraphRank.html
  2. ↑ Grossman, Jerrold W.; Kulkarni, Devadatta M.; Schochetman, Irwin E. (1995), "On the minors of an incidence matrix and its Smith normal form", Linear Algebra and its Applications 218: 213–224, doi:10.1016/0024-3795(93)00173-W, MR 1324059. See in particular the discussion on p. 218.

References