On the nullity number of graphs

Mustapha Aouchiche (GERAD and HEC Montreal, Canada)
Pierre Hansen (GERAD and HEC Montreal, Canada)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 5, No 2 (2017): Electronic Journal of Graph Theory and Applications

The paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 (2007) 60--67] that $\eta \le n - D$, where $\eta$, n and D denote the nullity number, the order and the diameter of a connected graph, respectively. We first give a necessary condition on the extremal graphs corresponding to that bound, and then we strengthen the bound itself using the maximum clique number. In addition, we prove bounds on the nullity using the number of pendant neighbors in a graph. One of those bounds is an improvement of a known bound involving the domination number.