The leaf-free graphs with nullity 2c(G)-1

Let G be a simple graph with n(G) vertices and e(G) edges. The elementary cyclic number c(G) of G is defined as c(G) = e(G) - n(G)+omega(G), where omega(G) is the number of connected components of G. The nullity of G, denoted by eta(G), is the multiplicity of the eigenvalue zero of the adjacency matrix of G. A graph is leaf-free if it has no pendent vertices. In Ma et al. (2016) proved that if G is leaf-free and each component of G contains at least two vertices, then eta(G) <= 2c(G), the equality is attained if and only if G is the union of disjoint cycles, where each cycle has length a multiple of 4. In this paper, we completely characterize all leaf-free graphs with nullity one less than the above upper bound, i.e., eta(G) = 2c(G) - 1. (C) 2019 Elsevier B.V. All rights reserved.