Counting maximal matchings in some classes of graphs
Tomislav Do\v{s}li\'c
University of Zagreb
PDF
Minisymposium: CHEMICAL GRAPH THEORY
Content: A matching $M$ in a graph $G$ is maximal if it cannot be extended to a larger matching in $G$. We show how several chemical and technical problems can be successfully modeled in terms of maximal matchings. Then we enumerate maximal matchings in several classes of graphs made by a linear or cyclic concatenation of basic building blocs. We also count maximal matchings in joins and corona products of some classes of graphs.