On Matchings in Graphs

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.