Sesión Matemática DiscretaEfecto de operaciones de vértices en asociaedros de grafos
Ana Gargantini
Facultad de Ciencias Exactas y Naturales de la Universidad Nacional de Cuyo y CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
El concepto de asociaedro de grafo abarca y generaliza familias conocidas de politopos, como los asociaedros clásicos, los permutoedros y los cicloedros. Dado un grafo conexo $G$, el asociaedro $\mathcal A(G)$ es un politopo convexo que codifica la estructura combinatoria de ciertas descomposiciones del grafo $G$ en grafos conexos más pequeños, y resulta una herramienta de utilidad en diversos contextos, tales como optimización, sistemas jerárquicos de visualización, generación de estructuras aleatorias y modelos probabilísticos. Además tienen relevancia en álgebra y física, ya que constituyen instancias particulares de permutoedros generalizados.
El $1$-esqueleto de $\mathcal A(G)$ se puede describir como el grafo de rotaciones de $G$, es decir, como el grafo $\mathcal R(G)$ cuyo conjunto de vértices es el conjunto de árboles de búsqueda sobre $G$ y cuyas aristas están determinadas por rotaciones en los árboles de búsqueda, y recibe el nombre de grafo de rotaciones de $G$. Entre las propiedades de interés estudiadas en estos grafos se encuentran aquellas relativas a hamiltonicidad, conectividad, coloreo y distancias.
En esta comunicación estudiamos cómo se reflejan en el grafo de rotaciones de $G$, algunas operaciones sobre el propio grafo $G$. En particular, consideramos las operaciones de añadir a $G$ un vértice pendiente, un gemelo falso o un gemelo verdadero. Presentamos resultados sobre la estructura de los grafos de rotaciones y sus consecuencias sobre las distancias en este grafo, así como también aplicaciones a su número cromático. Entre estos corolarios, demostramos que el número cromático de los asociaedros de grafos split completos es 3.
Trabajo en conjunto con: Adrián Pastine (Instituto de Matemática Aplicada San Luis, CONICET-UNSL) y Pablo Torres (Universidad Nacional de Rosario - CONICET).