Premium
Tutte sets in graphs I: Maximal tutte sets and D‐graphs
Author(s) -
Bauer D.,
Broersma H. J.,
Morgana A.,
Schmeichel E.
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20243
Subject(s) - combinatorics , mathematics , bipartite graph , discrete mathematics , iterated function , graph , mathematical analysis
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 ≅ D ( G ) and for which D ( G )≅ D 2 ( G ). Surprisingly, it turns out that for every graph G with a perfect matching, D 3 ( G )≅ D 2 ( G ). Finally, we characterize bipartite D ‐graphs and comment on the problem of characterizing D ‐graphs in general. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 343–358, 2007