Nullity (graph theory)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

The nullity of a graph in the mathematical subject of graph theory can mean either of two unrelated numbers. If the graph has n vertices and m edges, then: * In the matrix theory of graphs, the nullity of the graph is the nullity of the adjacency matrix A of the graph. The nullity of A is given by n − r where r is the rank of the adjacency matrix. This nullity equals the multiplicity of the eigenvalue 0 in the spectrum of the adjacency matrix. See Cvetkovič and Gutman (1972), Cheng and Liu (2007), and Gutman and Borovićanin (2011). * In the matroid theory the nullity of the graph is the nullity of the oriented incidence matrix M associated with the graph. The nullity of M is given by m − n + c, where, c is the number of components of the graph and n − c is the rank of the oriented incidence matrix. This name is rarely used; the number is more commonly known as the cycle rank, cyclomatic number, or circuit rank of the graph. It is equal to the rank of the cographic matroid of the graph. It also equals the nullity of the Laplacian matrix of the graph, defined as L = D − A, where D is the diagonal matrix of vertex degrees; the Laplacian nullity equals the cycle rank because L = M M T (M times its own transpose).

The nullity of a graph in the mathematical subject of graph theory can mean either of two unrelated numbers. If the graph has n vertices and m edges, then: In the matrix theory of graphs, the nullity of the graph is the nullity of the adjacency matrix A of the graph. The nullity of A is given by n − r where r is the rank of the adjacency matrix. This nullity equals the multiplicity of the eigenvalue 0 in the spectrum of the adjacency matrix. See Cvetkovič and Gutman (1972), Cheng and Liu (2007), and Gutman and Borovićanin (2011). In the matroid theory the nullity of the graph is the nullity of the oriented incidence matrix M associated with the graph. The nullity of M is given by m − n + c, where, c is the number of components of the graph and n − c is the rank of the oriented incidence matrix. This name is rarely used; the number is more commonly known as the cycle rank, cyclomatic number, or circuit rank of the graph. It is equal to the rank of the cographic matroid of the graph. It also equals the nullity of the Laplacian matrix of the graph, defined as L = D − A, where D is the diagonal matrix of vertex degrees; the Laplacian nullity equals the cycle rank because L = M M T (M times its own transpose).

See also

Rank (graph theory)

References

Bo Cheng and Bolian Liu (2007), On the nullity of graphs. Electronic Journal of Linear Algebra, vol. 16, article 5, pp. 60–67. Dragoš M. Cvetkovič and Ivan M. Gutman (1972), The algebraic multiplicity of the number zero in the spectrum of a bipartite graph. Matematički Vesnik (Beograd), vol. 9, pp. 141–150. Ivan Gutman and Bojana Borovićanin (2011), Nullity of graphs: an updated survey. Zbornik Radova (Beograd), vol. 14, no. 22 (Selected Topics on Applications of Graph Spectra), pp. 137–154.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1258128474 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.