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.

Back to all abstracts