DROPS

Document

Short Paper

DOI: 10.4230/LIPIcs.ITP.2019.36

Formalization of the Domination Chain with Weighted Parameters (Short Paper)

Authors: Daniel E. Severín

Published in: LIPIcs, Volume 141, 10th International Conference on Interactive Theorem Proving (ITP 2019)

Abstract

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.

Cite as

Daniel E. Severín. Formalization of the Domination Chain with Weighted Parameters (Short Paper). In 10th International Conference on Interactive Theorem Proving (ITP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 141, pp. 36:1-36:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{severin:LIPIcs.ITP.2019.36,
  author =	{Sever{\'\i}n, Daniel E.},
  title =	{{Formalization of the Domination Chain with Weighted Parameters}},
  booktitle =	{10th International Conference on Interactive Theorem Proving (ITP 2019)},
  pages =	{36:1--36:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-122-1},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{141},
  editor =	{Harrison, John and O'Leary, John and Tolmach, Andrew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2019.36},
  URN =		{urn:nbn:de:0030-drops-110919},
  doi =		{10.4230/LIPIcs.ITP.2019.36},
  annote =	{Keywords: Domination Chain, Coq, Formalization of Mathematics}
}

Search Results

Documents authored by Severín, Daniel E.

Formalization of the Domination Chain with Weighted Parameters (Short Paper)

Abstract

Cite as

Thanks for your feedback!

Could not send message