Descomposiciones de Kn y Kn−I en ciclos

Abstract

RESUMEN: Descomponer un grafo en ciclos consiste en proporcionar una partición disjunta de sus aristas, de modo que cada una de ellas pertenezca a un único ciclo. En particular, se estudiará el grafo completo Kn, el cual se desea descomponer en ciclos disjuntos Cm. Para que esta descomposición se pueda dar deben cumplirse una serie de condiciones que tienen que ver con el número de vértices del grafo y las longitudes de los ciclos. Entre ellas se encuentra que n tiene que ser impar. Es por ello que para poder abarcar el caso n par se deben estudiar las descomposiciones del grafo completo menos un 1-factor, esto es, el grafo Kn − I. En este trabajo se muestran varias descomposiciones de estos dos grafos mediante el empleo de diversas técnicas, determinando que las condiciones necesarias son además suficientes y ofreciendo una construcción para poder llegar a ellas. Del mismo modo se muestran ejemplos ilustrativos que permiten acompañar dichas construcciones y visualizar las descomposiciones.

ABSTRACT: Descomponer un grafo en ciclos consiste en proporcionar una partición disjunta de sus aristas, de modo que cada una de ellas pertenezca a un único ciclo. En particular, se estudiará el grafo completo Kn, el cual se desea descomponer en ciclos disjuntos Cm. Para que esta descomposición se pueda dar deben cumplirse una serie de condiciones que tienen que ver con el número de vértices del grafo y las longitudes de los ciclos. Entre ellas se encuentra que n tiene que ser impar. Es por ello que para poder abarcar el caso n par se deben estudiar las descomposiciones del grafo completo menos un 1-factor, esto es, el grafo Kn − I. En este trabajo se muestran varias descomposiciones de estos dos grafos mediante el empleo de diversas técnicas, determinando que las condiciones necesarias son además suficientes y ofreciendo una construcción para poder llegar a ellas. Del mismo modo se muestran ejemplos ilustrativos que permiten acompañar dichas construcciones y visualizar las descomposiciones.