Article
Generalizing D-graphs
Discrete Applied Mathematics
(2007)
Abstract
Let ω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 |), 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) = ω0 (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.
Keywords
- Matching,
- D-graph,
- Tutte set,
- Barrier set,
- Extreme set
Disciplines
Publication Date
November 1, 2007
DOI
10.1016/j.dam.2007.06.017
Citation Information
Arthur Busch, Michael Ferrara and Nathan Kahl. "Generalizing D-graphs" Discrete Applied Mathematics Vol. 155 Iss. 18 (2007) p. 2487 - 2495 ISSN: 1872-6771 Available at: http://works.bepress.com/nathan-kahl/8/