Propiedades del diferencial en gráficas

Abstract

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.