An improved lower bound for the nullity of a graph in terms of matching number
Xiaobin Ma, Xianwen Fang · Linear and Multilinear Algebra · 2019
Let G be a connected undirected graph without loops and multiple edges. By |G|, η(G), and m(G) we, respectively, denote the order, the nullity, and the matching number of G. Let c(G)=|E(G)|−|G|+1, and let θ(G) be a nonnegative integer defined as: To make G to be a bipartite connected graph at least θ(G) edges of G must be deleted from G. In this note, applying an operation called bipartite double, we prove that |G|−2m(G)−θ(G)≤η(G) for an arbitrary connected graph G. This result improves a main result in Wang and Wong [Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank. Disc Appl Math. 2014;166:276–281] saying that |G|−2m(G)−c(G)≤η(G) for a connected graph G.