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

Bauer, D. and Broersma, H.J. and Morgana, A. and Schmeichel, E. (2007) Tutte sets in graphs I: Maximal tutte sets and D-graphs. Journal of Graph Theory, 55 (4). pp. 343-358. ISSN 0364-9024

PDF
Restricted to UT campus only: Request a copy
177Kb

Abstract:	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.
Item Type:	Article
Copyright:	© 2007 Wiley
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/61765
Official URL:	http://dx.doi.org/10.1002/jgt.20243
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 241719