Inclusion maximal matchings
Marek Karpiński, Wojciech Rytter · 1998
Abstract In this chapter we consider matchings M which are maximal with respect to inclusion. This means that in a given graph G there is no matching M’ ≠. M such that M ⊂ M’. If X is a set of vertices then denote by Incident(X) the set of edges incident to any vertex in X. Denote also the set of edges incident with any endpoint of an edge in M by Incident(M); hence M ⊆ Incident(M). Observation Let M be a set of independent edges, and X be the set of endpoints of edges in M. Then the following conditions are equivalent: (a)M is an inclusion maximal matching. (b) E = Incident(M). (c) E = Incident(X).