Rank (graph theory)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In graph theory, a branch of mathematics, the rank of an undirected graph is defined as the number nc, 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 mn + 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[edit]

Notes[edit]

  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[edit]

  • Chen, Wai-Kai (1976), Applied Graph Theory, North Holland Publishing Company, ISBN 0-7204-2371-6 .