On the nullity of graphs

By Bo Cheng, Bolian Liu. 2007

144 citations recorded by the source corpus.

The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. It is known that η(G) ≤ n − 2 if G is a simple graph on n vertices and G is not isomorphic to nK1. In this paper, we characterize the extremal graphs attaining the upper bound n− 2 and the second upper bound n− 3. The maximum nullity of simple graphs with n vertices and e edges, M(n, e), is also discussed. We obtain an upper bound of M(n, e), and characterize n and e for which the upper bound is achieved.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Organic Chemistry

View Paper: https://www.semanticscholar.org/paper/c6f1a04d66ce8419f98c925cfdacdfad1d39f4fd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Gerard Jennhwa Chang
2. Hong-Gwa Yeh
3. Liang-Hao Huang

In Geometry and Topology

1. Gerard Jennhwa Chang
2. Hong-Gwa Yeh
3. Liang-Hao Huang

In Organic Chemistry

1. Gerard Jennhwa Chang
2. Hong-Gwa Yeh
3. Liang-Hao Huang

Citations in the corpus

• A characterization of graphs with rank 5 (2012, background): “For a connected graph G on n vertices, it was shown in [27] (see also [8,18]) that r(G) = 2 if and only if G is isomorphic to a complete bipartite graph Ka,b, where a + b = n, a, b > 0.”