El diferencial de gráficas con cuello dado

Ponente(s): Paloma Araceli Lazo Larios, Cristo Tristan Cobos Vera, Universidad Autónoma de Estado de Hidalgo Paloma Araceli Lazo Larios, Universidad Autónoma Metropolitana Unidad Cuajimalpa Sebastián Franco Martínez. Universidad Autónoma Metropolitana Unidad Cuajimalpa Citlali Amairani Herrera Ramírez, Universidad Veracruzana Mika Olsen, Universidad Autónoma Metropolitana Unidad Cuajimalpa Diego Antonio González Moreno, Universidad Autónoma Metropolitana Unidad Cuajimalpa

Para explicar el concepto de diferencial, consideramos un juego cuyo tablero es una gráfica G. En este juego se pueden comprar tantas fichas como se quiera, por ejemplo k, y colocarlas sobre un subconjunto de k vértices de G. Por cada vértice que no tenga una ficha encima y que sea adyacente a un vértice con una ficha recibes $1. El objetivo es maximizar la ganancia. Para formalizar el estudio del diferencial de una gráfica G se define la frontera de un subconjunto de vértices X\subset V(G) como B(X)=V(G)\setminus X\cap N(X), donde N(X) es la vecindad del conjunto X, es decir, el conjunto de vértices adyacentes a algún vértice de X. Así, el diferencial de X se define como |B(X)|-|X|, y el diferencial de G es el máximo diferencial entre todos los subconjuntos de V(G). En este trabajo se estudia el diferencial de las gráficas con cuello g. Se presentan cotas inferiores para el diferencial de una gráfica en términos del grado máximo, el grado mínimo y el cuello. Se analizan las consecuencias de estas cotas en gráficas regulares y en la familia de las jaulas. Finalmente se propone una conjetura para el diferencial de una jaula de Moore, la cual fue verificada para la graficas de Petersen, Heawood y Wong.