Formalization of the Domination Chain with Weighted Parameters

The Cockayne-Hedetniemi Domination Chain is a chain of inequalities between classic parameters of graph theory: for a given graph G, ir(G) ≤ γ(G) ≤ ι(G) ≤ α(G) ≤ Γ(G) ≤ IR(G). These parameters return the maximum/minimum cardinality of a set satisfying some property. However, they can be generaliz...

Descripción completa

Detalles Bibliográficos
Autor principal: Severín, Daniel Esteban
Otros Autores: LIPIcs – Leibniz International Proceedings in Informatics
Formato: conferenceObject documento de conferencia publishedVersion
Lenguaje:Inglés
Publicado: 2020
Materias:
Mathematics of computing
Graph theory
https://purl.org/becyt/ford/1.1
Domination Chain
Coq
Formalization of Mathematics
Acceso en línea:http://hdl.handle.net/2133/18978
http://hdl.handle.net/2133/18978
Aporte de:
Repositorio Hipermedial de la Universidad Nacional de Rosario (UNR) de Universidad Nacional de Rosario
id I15-R121-2133-18978
record_format dspace
institution Universidad Nacional de Rosario
institution_str I-15
repository_str R-121
collection Repositorio Hipermedial de la Universidad Nacional de Rosario (UNR)
language Inglés
orig_language_str_mv eng
topic Mathematics of computing
Graph theory
https://purl.org/becyt/ford/1.1
Domination Chain
Coq
Formalization of Mathematics
spellingShingle Mathematics of computing
Graph theory
https://purl.org/becyt/ford/1.1
Domination Chain
Coq
Formalization of Mathematics
Severín, Daniel Esteban
Formalization of the Domination Chain with Weighted Parameters
topic_facet Mathematics of computing
Graph theory
https://purl.org/becyt/ford/1.1
Domination Chain
Coq
Formalization of Mathematics
description The Cockayne-Hedetniemi Domination Chain is a chain of inequalities between classic parameters of graph theory: for a given graph G, ir(G) ≤ γ(G) ≤ ι(G) ≤ α(G) ≤ Γ(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.
author2 LIPIcs – Leibniz International Proceedings in Informatics
author_facet LIPIcs – Leibniz International Proceedings in Informatics
Severín, Daniel Esteban
format conferenceObject
documento de conferencia
publishedVersion
author Severín, Daniel Esteban
author_sort Severín, Daniel Esteban
title Formalization of the Domination Chain with Weighted Parameters
title_short Formalization of the Domination Chain with Weighted Parameters
title_full Formalization of the Domination Chain with Weighted Parameters
title_fullStr Formalization of the Domination Chain with Weighted Parameters
title_full_unstemmed Formalization of the Domination Chain with Weighted Parameters
title_sort formalization of the domination chain with weighted parameters
publishDate 2020
url http://hdl.handle.net/2133/18978
http://hdl.handle.net/2133/18978
work_keys_str_mv AT severindanielesteban formalizationofthedominationchainwithweightedparameters
bdutipo_str Repositorios
_version_ 1764820409996279810

Ejemplares similares