Computer assisted discovery: Zero forcing vs vertex cover

Abstract

In this paper, we showcase the process of using an automated conjecturing program called \emph{TxGraffiti} written and maintained by the second author. We begin by proving a conjecture formulated by \emph{TxGraffiti} that for a claw-free graph $G$, the vertex cover number $\beta (G)$ is greater than or equal to the zero forcing number $Z(G)$. Our proof of this result is constructive, and yields a polynomial time algorithm to find a zero forcing set with cardinality $\beta (G)$. We also use the output of \emph{TxGraffiti} to construct several infinite families of claw-free graphs for which $Z(G)=\beta (G)$. Additionally, inspired by the aforementioned conjecture of \emph{TxGraffiti}, we also prove a more general relation between the zero forcing number and the vertex cover number for any connected graph with maximum degree $\Delta \ge 3$, namely that $Z(G)\le (\Delta -2)\beta (G)$+1.

Feedback welcome!