Please use this identifier to cite or link to this item: http://infotec.repositorioinstitucional.mx/jspui/handle/1027/201
Sobre las extensiones finitas de gráficas
Natalia García-Colín
Miguel Ángel Pizaña
Rafael Villarroel-Flores
Acceso Abierto
Atribución-NoComercial-SinDerivadas
Extensiones finitas
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.
XXX Coloquio Víctor Neumann-Lara de Teoría de Gráficas, Combinatoria y sus Aplicaciones
2015
Artículo
Español
Investigadores
OTRAS
Appears in Collections:Artículos

Upload archives


File Description SizeFormat 
Sobre las extensiones finitas de gr´aficas.pdf390.12 kBAdobe PDFView/Open