Graphs with large maximum forcing number

Abstract

For a graph $G$ with order $2n$ and a perfect matching, let $f(G)$ and $F(G)$ denote the minimum and maximum forcing number of $G$ respectively. Then $0\le f(G)\le F(G)\le n-1$. Liu and Zhang [10] ever proposed a conjecture: $e(G)\ge \frac{n^2}{n-F(G)}$, where $e(G)$ denotes the number of edges of $G$. In this paper we confirm this conjecture and obtain $F(G)\le n-\frac{n^2}{e(G)}$. If $F(G)=n-1$, Liu and Zhang [9] proved that any two perfect matchings of $G$ can be obtained from each other by a series of matching switches along 4-cycles. If $G$ is bipartite and $F(G)\ge n-k$, $1\le k\le n-1$, we show that any two perfect matchings of $G$ can be obtained from each other by a series of matching switches along even cycles of length at most $2(k+1)$. Finally, we ask whether $f(G)\ge \lceil \frac{n}{k}\rceil -1$ holds for such bipartite graphs $G$, and give positive answers for the cases $k=1,2$. Further we show all minimum forcing numbers of the bipartite graphs $G$ of order $2n$ and with $F(G)=n-2$ form an integer interval $[\lfloor \frac{n}{2}\rfloor ,n-2]$.