On Matchings in Graphs

Abstract

A matching in a graph $G$ is a set of independent edges and a maximal matching is a matching that is not properly contained in any other matching in $G$. A maximum matching is a matching of maximum cardinality. The number of edges in a maximum matching is denoted by ${\beta }_1(G)$; while the number of edges in a maximal matching of minimum cardinality is denoted by ${\beta }_1^{-}(G)$. Several results concerning these parameters are established including a Nordhaus-Gaddum result for ${\beta }_1^{-}(G)$. Finally, in order to compare the maximum matchings in a graph $G$, a metric on the set of maximum matchings of $G$ is defined and studied. Using this metric, we define a new graph $M(G)$, called the matching graph of $G$. Several graphs are shown to be matching graphs; however, it is shown that not all graphs are matching graphs.