Abstract:
We are interested in the problem of which graphs on \(n\) vertices with \(m\) edges have the maximum and minimum number of matchings. It is known that among all graphs, the graphs minimizing the number of matchings are threshold graphs. These are graphs that can be constructed in stages from one vertex by adding either a dominant vertex or an isolated vertex at each stage. To get a better understanding of this topic we will look at how to maximize the number of matchings over all threshold graphs. We will define what it means to be an almost alternating threshold graph and show that a threshold graph has the maximum number of matchings if and only if it is almost alternating.