On the König-Egerváry Index of a Graph

A graph is said to beK\H{o}nig-Egerv\'{a}ry if its matching number equals its covering number. The difference between these two graph parameters, covering minus matching number, measures in some sense, how far a graph is from being a K\H{o}nig-Egerv\'{a}ry graph. Several properties of this difference, called the K\H{o}nig-Egerv\'{a}ry index or K\H{o}nig deficiency, are presented, including some non-trivial structural characterizations. Furthermore, it is shown that various statements involving K\H{o}nig-Egerv\'{a}ry graphs are, in fact, general statements about graphs that can be expressed in terms of their K\H{o}nig-Egerv\'{a}ry indices.