The extremal graphs with respect to their nullity

Abstract

Abstract The nullity of a graph G, denoted by η ( G ) $\eta(G)$ , is the multiplicity of the eigenvalue zero of its adjacency matrix. In this paper, we determine all graphs with η ( G ) = n ( G ) − 2 m ( G ) − c ( G ) $\eta(G)=n(G) - 2m(G) -c(G)$ , where c ( G ) = e ( G ) − n ( G ) + ω ( G ) $c(G) = e(G) - n(G) + \omega(G)$ , and n ( G ) $n(G)$ , e ( G ) $e(G)$ , m ( G ) $m( G )$ , and ω ( G ) $\omega (G)$ are the vertex number, edge number, matching number, and the number of connected components of G, respectively.

Keywords

• nullity of graph
• matching number