An improved lower bound for the nullity of a graph in terms of matching number

Abstract

Let G be a connected undirected graph without loops and multiple edges. By $|G|,\eta \left(G\right)$, and $m\left(G\right)$ we, respectively, denote the order, the nullity, and the matching number of G. Let $c\left(G\right)=|E\left(G\right)|-|G|+1$, and let $\theta \left(G\right)$ be a nonnegative integer defined as: To make G to be a bipartite connected graph at least $\theta \left(G\right)$ edges of G must be deleted from G. In this note, applying an operation called bipartite double, we prove that $|G|-2m\left(G\right)-\theta \left(G\right)\le \eta \left(G\right)$ 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\left(G\right)-c\left(G\right)\le \eta \left(G\right)$ for a connected graph G.

COMMUNICATED BY:

• J.Y. Shao

Keywords:

• Nullity
• matching number
• bipartite double

2010 Mathematics Subject Classification:

• 05C50

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by Educational Commission of Anhui Province of China [grant number KJ2018A0081]; National Natural Science Foundation of China[grant number 61572035].