Generalizing D-graphs Original Research Article

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