Tutte sets in graphs I: Maximal tutte sets and D-graphs

D. Bauer, Haitze J. Broersma, A. Morgana, E. Schmeichel

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
22 Downloads (Pure)


A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph $G$ in terms of what is usually called the deficiency of $G$. A subset $X$ of $V(G)$ for which this deficiency is attained is called a Tutte set of $G$. While much is known about maximum matchings, less is known about the structure of Tutte sets. In this article, we study the structural aspects of maximal Tutte sets in a graph $G$. Towards this end, we introduce a related graph $D(G)$. We first show that the maximal Tutte sets in $G$ are precisely the maximal independent sets in its $D$-graph $D(G)$, and then continue with the study of $D$-graphs in their own right, and of iterated $D$-graphs. We show that $G$ is isomorphic to a spanning subgraph of $D(G)$, and characterize the graphs for which $G\cong D(G)$ and for which $D(G)\cong D^2(G)$. Surprisingly, it turns out that for every graph $G$ with a perfect matching, $D^3(G)\cong D^2(G)$. Finally, we characterize bipartite $D$-graphs and comment on the problem of characterizing $D$-graphs in general.
Original languageUndefined
Article number10.1002/jgt.20243
Pages (from-to)343-358
Number of pages16
JournalJournal of graph theory
Issue numberSINTEF A13/4
Publication statusPublished - Mar 2007


  • EWI-10335
  • IR-61765
  • METIS-241719

Cite this