Search

Sea G = (V (G), E(G)) una gráfica simple, en el que V (G) y E(G) son sus conjuntos de vértices y aristas respectivamente. Si S ⊆ V (G), sea B(S) el conjunto de vértices con- tenido en V (G)\S con algún vecino en S. El diferencial de S denotado por ∂(S) se define como |B(S)| −|S|, y el diferencial de una gráfica como ∂(G) = m ́ax{∂(S) : S ⊆ V (G)}. En este trabajo mostramos una amplia colección de resultados que relacionan el dife- rencial con parámetros bien conocidos, como el número de dominación, orden, tamaño, grado, cuello, entre otros. También estudiamos el diferencial en la gráfica R(G), que se obtiene a partir de G, agregando un nuevo vértice por cada arista de G y uniendo cada vértice nuevo a los extremos de la arista correspondiente a él. Encontramos cotas para ∂(R(G)) y familias infinitas de gráficas que las alcanzan. Además, mostramos relaciones interesantes entre ciertos conjuntos de vértices de G y R(G). Generalizamos el concepto de diferencial de una gráfica. Estudiamos las propiedades matemáticas de este nuevo parámetro y encontramos cotas que lo relacionan con el orden, tamaño, grado mínimo (máximo) y el número de dominación. Finalmente, este trabajo se complementa con el concepto de polinomio diferencial, establecemos relaciones entre el polinomio y sus coeficientes, y mostramos fórmulas del polinomio diferencial en ciertas clases de gráficas.

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].