Characterization of graphs with given order, given size and given matching number that minimize nullity

摘要

Let G = (V(G), E(G)) be a finite undirected graph without loops and multiple edges, c(G) = vertical bar E(G)vertical bar - vertical bar V(G)vertical bar + theta(G) be the dimension of cycle spaces of G with theta(G) the number of connected components of G, m(G) be the matching number of G, and eta(G) be the nullity of G. It was shown in Wang and Wong (2014) that the nullity eta(G) of G is bounded by an upper bound and a lower bound as