Bounds on the Complete Forcing Numbers of Graphs

Abstract

A complete forcing set of a graph is a subset $S$ of its edges with the following property. For any perfect matching $M$, $M$ is the unique perfect matching containing the intersection of $M$ and $S$. The size of a smallest complete forcing set of a graph is called its complete forcing number. In this paper, we propose a polynomial-time algorithm that takes a graph and an ordering of its vertices as input, and outputs a complete forcing set. We analyze the size of the output for a carefully chosen ordering to derive an upper bound on the complete forcing numbers of graphs in terms of other graph-theoretical parameters, such as the degeneracy and the spectral radius of the underlying graph. We compare our results with previous findings in the field. For the class of edge-transitive graphs, we provide an explicit lower bound on the complete forcing number. This result is applied in particular to hypercube graphs and Cartesian powers of even cycles.

arXiv comment20 pages