Originator: Stephen Hartke (presented by S. Hartke - REGS 2010)
Definitions: A realization of a nonnegative integer list d is a graph (no loops or multiple edges) whose vertex degrees are the entries in d. A list is graphic if it has a realization.
Background: For each graphic list d, Alon and Friedman [AF] determined the maximum number of perfect matchings in a realization of d.
Question: Given a graphic list d, what is the minimum number of perfect matchings in a realization of d?
Comments: Gross, Kahl, and Saccoman [GKS] determined the minimum and maximum number of perfect matchings among graphs with fixed numbers of vertices and edges.
One way to approach this problem is to start by determining the graphic lists for which every realization contains a perfect matching. This can begin by determining the maximum number of edges in an n-vertex graph with minimum degree k that has no perfect matching. By Tutte's Theorem [T], such a graph has a vertex subset S (called a Tutte set) such that o(G-S)>|S|, where o(H) is the number components of H having an odd number of vertices. Among the n-vertex graphs with minimum degree k having a Tutte set (with n even and k<n/3), the maximum number of edges is achieved using a Tutte set S of size k such that deleting S leaves k+1 isolated vertices and one complete subgraph with n-2k-1 vertices.
[DBvdHKS] give a best monotone characterization of graphic lists for which every realization has a perfect matching. Their result generalizes work of Las Vergnas and of Bondy and Chvátal. Ostrand [O] determined the minimum number of perfect matchings in bipartite graph on vertex set X∪Y where the degrees in X are specified. Hwang [H] gave another proof of this result.
It is worth noting that one can ask this question for any graph parameter, say ρ(G). That is, given a graphic list d, what are the maximum and minimum possible values of ρ(G) when G is a realization of d? Furthermore, one can ask the "Interpolation Question": are all values between the minimum and the maximum achievable?
References:
[AF] N. Alon, S. Friedland, The maximum number of perfect matchings in graphs
with a given degree sequence,
Electron. J. Combin. 15 (2008) N13.
[DBvdHKS] D. Bauer, H.J. Broersma, J. van den Heuvel, N. Kahl, E. Schmeichel,
Degree Sequences and the Existence of $k$-Factors,
arXiv:0912.2916v1.
[GKS] D. Gross, N. Kahl, J. T. Saccoman, Graphs with the maximum or
minimum number of 1-factors. Discrete Math. 310 (2010), no. 4, 687--691.
[H] S.-G. Hwang, A note on system of distinct representatives.
Kyungpook Math. J. 35 (1996), no. 3, Special Issue, 513--516.
[O] P.A. Ostrand,
Systems of distinct representatives. II.
J. Math. Anal. Appl. 32 1970 1--4.
[T] W.T. Tutte, The factorization of linear graphs.
J. London Math. Soc. 22, (1947). 107--111.