The nullity of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

in the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

subject of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

can mean either of two unrelated numbers. If the graph has ''n'' vertices and ''m'' edges, then: * In the

matrix theory In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object. For example, \beg ...

of graphs, the nullity of the graph is the nullity of the

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...

''A'' of the graph. The nullity of ''A'' is given by ''n'' − ''r'' where ''r'' is the

rank Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * H ...

of the adjacency matrix. This nullity equals the multiplicity of the

eigenvalue In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denot ...

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 In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

the nullity of the graph is the nullity of the oriented

incidence matrix In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...

''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

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 In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycle (graph theory), cycles, making ...

of the graph. It is equal to the rank of the co

graphic matroid In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called c ...

of the graph. It also equals the nullity of the

Laplacian matrix In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Lapl ...

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

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. Graph theory {{graph-stub

See also

References