Generalizing D-graphs

Let ω₀(G) denote the number of odd components of a graph G. The deficiency of G is defined as def(G)=max_X⊆V(G)(ω₀(G-X)-|X|), and this equals the number of vertices unmatched by any maximum matching of G. A subset X⊆V(G) is called a Tutte set (or barrier set) of G if def(G)=ω₀(G-X)-|X|, and an extreme set if def(G-X)=def(G)+|X|. Recently a graph operator, called the D-graph 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.