On the Kőnig–Egerváry index of a graph

A graph is said to be Kőnig–Egerváry if its matching number equals its vertex cover number. The difference between these two graph parameters, the vertex cover number minus the matching number, measures, in some sense, how far a graph is from being a Kőnig–Egerváry graph. Several properties of this difference, called the Kőnig–Egerváry index or Kőnig deficiency, are presented, including some nontrivial structural characterizations. Furthermore, it is shown that various statements involving Kőnig–Egerváry graphs are, in fact, general statements about graphs that can be expressed in terms of their Kőnig–Egerváry indices.