Graphs G with nullity 2c(G) plus p(G)-1

The nullity eta(G) of a (simple) graph G is the multiplicity of O 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, eta(G) <= 2c(G) + p(G) - 1, where c(G) = e(G) - n(G) + theta(G) is the cyclomatic number of G, theta(G) being the number of connected components of G. In this paper connected graphs G and trees T that satisfy respectively the conditions eta(G) = 2c(G)+p(G)-1 and eta(T) = p(T)-1 are characterized. Besides, we identify the matched and mismatched vertices in a tree T that satisfies eta(T) = p(T) - 1 and characterize trees T that have a pendant vertex matched in T and satisfy eta(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 eta(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}. (C) 2022 Elsevier B.V. All rights reserved.