Maximizing the Minimum and Maximum Forcing Numbers of Perfect Matchings of Graphs

Let G be a simple graph with 2n vertices and a perfect matching. The forcing number f(G, M) of a perfect matching M of G is the smallest cardinality of a subset of M that is contained in no other perfect matching of G. Among all perfect matchings M of G, the minimum and maximum values of f(G, M) are called the minimum and maximum forcing numbers of G, denoted by f(G) and F (G), respectively. Then f(G) ≤ F (G) ≤ n − 1. Che and Chen (2011) proposed an open problem: how to characterize the graphs G with f(G) = n − 1. Later they showed that for a bipartite graph G, f(G)= n − 1 if and only if G is complete bipartite graph Kn,n. In this paper, we completely solve the problem of Che and Chen, and show that f(G)= n − 1 if and only if G is a complete multipartite graph or a graph obtained from complete bipartite graph Kn,n by adding arbitrary edges in one partite set. For all graphs G with F (G) = n − 1, we prove that the forcing spectrum of each such graph G forms an integer interval by matching 2-switches and the minimum forcing numbers of all such graphs G form an integer interval from ⌊n2⌋\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lfloor{n\over 2}\rfloor$$\end{document} to n − 1.