Relation between the nullity of a graph and its matching number (Q833002)

Let \(G\) be a connected graph of order \(n(G)\) and size \(e(G)\). The nullity of \(G\), denoted by \(\eta(G)\), is the multiplicity of eigenvalue zero of the adjacency matrix of \(G\). \textit{L. Wang} and \textit{D. Wong} [ibid. 166, 276--281 (2014; Zbl 1283.05226)] bounded \(\eta(G)\) as \[ n(G)-2m(G)-c(G) \le\eta(G) \le n(G)-2m(G) + 2c(G), \] where \(m(G)\) is the matching number of \(G\) and \(c(G)\), defined by \(c(G) = e(G)-n(G) + 1\), is the dimension of cycle space of \(G\). The authors found that the upper and the lower bounds for \(\eta(G)\) both fail to accurate if the edges in \(G\) are dense, namely if \(c(G)\) is large enough. In this paper, the authors improved the above bounds. They proved that \[ n(G)-2m(G)-\sigma(G) \le \eta(G)\le n(G)-2m(G) + 2\omega(G), \] where \(\sigma(G)\) is the largest number of disjoint odd cycles in \(G\) and \(\omega(G)\) is the number of even cycles in \(G\). The cycle-disjoint connected graphs with nullity \(n(G)-2m(G)-\sigma(G)\) were also characterized.