论文标题
计算机辅助发现：零强制与顶点盖
Computer assisted discovery: Zero forcing vs vertex cover
论文作者
论文摘要
在本文中，我们展示了使用第二作者编写和维护的称为\ emph {txgraffiti}的自动猜想程序的过程。首先，我们证明了由\ emph {txgraffiti}提出的猜想，即对于无爪图$ g $，顶点封面数$β（g）$大于或等于零强迫$ z（g）$。我们对此结果的证明是建设性的，并且产生多项式时间算法，以找到具有基数$β（g）$的零强迫。我们还使用\ emph {txgraffiti}的输出来构造几个无限的无爪图系列，其中$ z（g）=β（g）$。此外，灵感来自上述\ emph {txgraffiti}的猜想，我们还证明，对于任何连接的图形，零强制数与最高$δ\ ge 3 $的顶点盖号之间的关系更加一般，即$ z（g）\ leq（g）\ leq（δ-2）$+1 $+1 $+1。
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 $β(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 $β(G)$. We also use the output of \emph{TxGraffiti} to construct several infinite families of claw-free graphs for which $Z(G)=β(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 $Δ\ge 3$, namely that $Z(G)\leq (Δ-2)β(G)$+1.
