文章基本信息

标题：Formalization of the Domination Chain with Weighted Parameters (Short Paper)
本地全文：下载
作者：Daniel E. Sever{\'\i}n
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：141
页码：1-7
DOI：10.4230/LIPIcs.ITP.2019.36
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The Cockayne-Hedetniemi Domination Chain is a chain of inequalities between classic parameters of graph theory: for a given graph G, ir(G) <= gamma(G) <= iota(G) <= alpha(G) <= Gamma(G) <= IR(G). These parameters return the maximum/minimum cardinality of a set satisfying some property. However, they can be generalized for graphs with weighted vertices where the objective is to maximize/minimize the sum of weights of a set satisfying the same property, and the domination chain still holds for them. In this work, the definition of these parameters as well as the chain is formalized in Coq/Ssreflect.
关键词：Domination Chain; Coq; Formalization of Mathematics