Groupe d’études et de recherche en analyse des décisions

G-2016-126

On the nullity number of graphs

et

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.

, 13 pages