Back

On the nullity number of graphs

Mustapha Aouchiche and Pierre Hansen

BibTeX reference

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

Document

G16126.pdf (400 KB)