Generalizing D-graphs

Let ω0(G)ω0(G) denote the number of odd components of a graph G. The deficiency of G   is defined as def(G)=maxX⊆V(G)(ω0(G-X)-|X|)def(G)=maxX⊆V(G)(ω0(G-X)-|X|), and this equals the number of vertices unmatched by any maximum matching of G  . A subset X⊆V(G)X⊆V(G) is called a Tutte set (or barrier set) of G   if def(G)=ω0(G-X)-|X|def(G)=ω0(G-X)-|X|, and an extreme set if def(G-X)=def(G)+|X|def(G-X)=def(G)+|X|. Recently a graph operator, called the D  -graph D(G)D(G), was defined that has proven very useful in examining Tutte sets and extreme sets of graphs which contain a perfect matching. In this paper we give two natural and related generalizations of the D-graph operator to all simple graphs, both of which have analogues for many of the interesting and useful properties of the original.