Graphs G with nullity 2c(G)+p(G

The nullity η(G) of a (simple) graph G is the multiplicity of 0 as an eigenvalue of the adjacency matrix of G. It was shown by Ma et al. (2016) that for a connected graph G with n(G) vertices, e(G) edges and p(G)(≥1) pendant vertices, η(G)≤2c(G)+p(G)−1, where c(G)=e(G)−n(G)+θ(G) is the cyclomatic number of G, θ(G) being the number of connected components of G. In this paper connected graphs G and trees T that satisfy respectively the conditions η(G)=2c(G)+p(G)−1 and η(T)=p(T)−1 are characterized. Besides, we identify the matched and mismatched vertices in a tree T that satisfies η(T)=p(T)−1 and characterize trees T that have a pendant vertex matched in T and satisfy η(T)=p(T)−2. We obtain new sharp lower and upper bounds for a tree T with p(T)≥3, given in terms of p(T) and the numbers of two special kinds of internal paths in T. It is also proved that for any integer c≥2, the set of values attained by η(G)−n(G)+2m(G), as G runs through all connected, leaf-free graphs G with cyclomatic number c, is {−c+1,−c+2,…,2c−3,2c−2}.