论文标题
使用半决赛编程和平方和总和的计算证据
Towards a Computational Proof of Vizing's Conjecture using Semidefinite Programming and Sums-of-Squares
论文作者
论文摘要
Viping的猜想（自1968年以来开放）将两个图的支配数字的乘积与其笛卡尔产品图的统治数相关联。在本文中，我们将Viping的猜想描述为一个阳性的存在问题。特别是，我们根据图形的顶点数量及其主导数量选择一类，并将猜想编码为理想/多项式对，以使多项式对与理想相关的多样性无负，仅当猜想为此图形类别为真时。使用半决赛编程，我们获得了数字总数证书，然后我们设法将其转换为符号证书，确认了多项式的非负性。具体而言，我们为特定图形类别获得了精确的低度稀疏平方总和证书。 获得的证书允许对较大的图类类的概括。除了对这些更一般证书的计算验证外，我们还提出了理论证明以及猜想和问题以进行进一步研究。
Vizing's conjecture (open since 1968) relates the product of the domination numbers of two graphs to the domination number of their Cartesian product graph. In this paper, we formulate Vizing's conjecture as a Positivstellensatz existence question. In particular, we select classes of graphs according to their number of vertices and their domination number and encode the conjecture as an ideal/polynomial pair such that the polynomial is non-negative on the variety associated with the ideal if and only if the conjecture is true for this graph class. Using semidefinite programming we obtain numeric sum-of-squares certificates, which we then manage to transform into symbolic certificates confirming non-negativity of our polynomials. Specifically, we obtain exact low-degree sparse sum-of-squares certificates for particular classes of graphs. The obtained certificates allow generalizations for larger graph classes. Besides computational verification of these more general certificates, we also present theoretical proofs as well as conjectures and questions for further investigations.
