Números de dominación y empaquetamiento de ciertas gráficas de fichas

Abstract

Dada una gráfica G de orden n ≥ 3, se define a F2(G) como la gráfica cuyo conjunto de vértices consiste de todos los 2-subconjuntos de V (G), y dos vértices X, Y de F2(G) serán adyacentes si y solo si la diferencia simétrica de X y Y consta de dos vértices que son adyacentes en G. Hasta donde sabemos, la gráfica F2(G) fue introducida por Johns en 1988 [43]. Posteriormente, en 1991 Alavi et al. [2], la definieron con el nombre de gráfica de doble vértice. En 2002, T. Rudolph [62] redefinió la misma gráfica bajo el nombre de el cuadrado simétrico de G. Similarmente, si en lugar de los 2-subconjuntos de V (G), se consideran los k-subconjuntos de V (G), donde k є {2 ,..., n - 1}, entonces obtenemos la gráfica Fk(G) que se llama la k-potencia simétrica de G [9]. En [27] Fabila-Monroy et. al., a Fk(G) la llamaron gráfica de k-fichas de G. Como se puede verificar en [3, 4, 6, 8, 9, 17, 18, 27, 39, 48, 52, 37, 53, 62, 66, 67] y las referencias contenidas en esos artículos, el interés en las gráficas Fk(G) ha generado una gran cantidad de investigaciones en muchas ramas de las matemáticas discretas. Una de las líneas de investigación con mayor actividad consiste en estimar o determinar el valor exacto de diversos parámetros combinatorios de Fk(G). En este trabajo se presentan algunos resultados originales sobre la estimación de dos de estos parámetros: el número de dominación y el número de empaquetamiento de F2(Pn) y F3(Pn), en donde Pn denota a la gráfica camino de orden n. El resultado principal de esta tesis consiste en la determinación del valor exacto del número de empaquetamiento de F2(Pn). Este resultado tiene como consecuencia la confirmación de una conjetura de Rob Pratt sobre el tamaño máximo que puede tener un código binario de longitud n y peso constante 2 que es 1-corrector para una transposición adyacente, y ha sido publicado en [30]. En particular, esta conjetura proponía la función generatriz ordinaria correspondiente a la secuencia A085680 en la OEIS (The On-Line Encyclopedia of Integer Sequences) [59].