Maximizing the Minimum and Maximum Forcing Numbers of Perfect Matchings of Graphs
Maximizing the Minimum and Maximum Forcing Numbers of Perfect Matchings of Graphs
复制标题
DOI：
10.1007/s10114-023-1020-6
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Li-Yu Daisy Liu;He Ping Zhang
中科院分区：
文献类型：
--
作者：
Li-Yu Daisy Liu;He Ping Zhang
LetGbe a simple graph with 2nvertices and a perfect matching. The forcing numberf(G, M) of a perfect matchingMofGis the smallest cardinality of a subset ofMthat is contained in no other perfect matching ofG. Among all perfect matchingsMofG, the minimum and maximum values off(G, M) are called the minimum and maximum forcing numbers ofG, denoted byf(G) andF(G), respectively. Thenf(G) ≤F(G) ≤n− 1. Che and Chen (2011) proposed an open problem: how to characterize the graphsGwithf(G) =n− 1. Later they showed that for a bipartite graphG, f(G)=n− 1 if and only ifGis complete bipartite graphKn,n. In this paper, we completely solve the problem of Che and Chen, and show thatf(G)=n− 1 if and only ifGis a complete multipartite graph or a graph obtained from complete bipartite graphKn,nby adding arbitrary edges in one partite set. For all graphsGwithF(G) =n− 1, we prove that the forcing spectrum of each such graphGforms an integer interval by matching 2-switches and the minimum forcing numbers of all such graphsGform an integer interval fromton− 1.
