Título

Sobre las extensiones finitas de gráficas

Autor

Natalia García-Colín

Miguel Ángel Pizaña

Rafael Villarroel-Flores

Nivel de Acceso

Acceso Abierto

Licencia

http://creativecommons.org/licenses/by-nc-nd/4.0

Materias

Extensiones finitas - (LEM) CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA - (CTI) MATEMÁTICAS - (CTI) OTRAS ESPECIALIDADES MATEMÁTICAS - (CTI) OTRAS - (CTI)

Resumen o descripción

Una gráfica G es extensión de otra gráfica L, si para todo vértice v 2 G, la subgráfica inducida por los vecinos de v es isomorfa a L. El problema de la extensión finita (PEF) consiste decidir si existe alguna extensión finita G para una gráfica dada L. Es un problema abierto el determinar si el PEF es algorítmicamente soluble o no, pero todas las variantes interesantes del PEF que se han considerado han resultado ser algorítmicamente irresolubles. Reportamos en este documento parte del trabajo que hemos venido haciendo en torno del PEF. En particular, presentamos condiciones suficientes para que una gráfica dada no tenga extensión finita.

Editor

XXX Coloquio Víctor Neumann-Lara de Teoría de Gráficas, Combinatoria y sus Aplicaciones

Fecha de publicación

2015

Tipo de publicación

Artículo

Recurso de información

http://infotec.repositorioinstitucional.mx/jspui/handle/1027/201

Formato

application/pdf

Idioma

Español

Audiencia

Investigadores

Repositorio Orígen

Repositorio Institucional de INFOTEC

Descargas

1688