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

[img] PDF
Restricted to UT campus only
: Request a copy
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
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/61765
Official URL:https://doi.org/10.1002/jgt.20243
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 241719