UMA 2022
Un torneo es un digrafo que tiene un arco por cada par de vértices. Un torneo es transitivo si, dados tres vértices cualesquiera $a, b, c$ se verifica la transitividad, es decir si $(a,b)$ y $(b,c)$ son arcos del digrafo, entonces $(a,c)$ es un arco del digrafo. Todo torneo transitivo tiene una fuente y un sumidero. Consideramos torneos transitivos maximales por contención. El digrafo de intersección de torneos transitivos maximales $\tau$ se define de la siguiente manera:
V($\tau$(D)) es el conjunto de todos los torneos transitivos maximales de D.
A($\tau$(D)) es el conjunto de arcos definido por: si $T_1$ y $T_2$ son torneos transitivos maximales de D y $f_1, f_2, s_1, s_2$ son sus fuentes y sumideros correspondientes, entonces $T_1 \rightarrow T_2$ si y solo si $s_1, f_2\in T_1 \cap T_2$ y $f_1, s_2\notin T_1 \cap T_2$.
Un grafo es de indiferencia si tiene un orden de indiferencia, es decir un orden total en sus vértices $v_1,...,v_n$ tal que si $i \lt j \lt k$, $v_i \sim v_k$ entonces $v_i \sim v_j$ y $v_j \sim v_k$.
Fue probado en [1] que la clase de grafos de indiferencia es una clase cerrada respecto al operador clique. Un digrafo es un digrafo de indiferencia orientado si es un digrafo de indiferencia cuyos arcos fueron orientados de manera que si $v_1, v_2,v_3,...,v_n$ es un orden de indiferencia y $v_i \sim v_j$, $v_i \rightarrow v_j$ si y solo si $i \lt j$. En este trabajo se demuestra que la clase de grafos de indiferencia orientados es una clase cerrada respecto al operador $\tau$.
Trabajo en conjunto con: Marisa Gutierrez (Centro de Matemática, Universidad Nacional de La Plata, Argentina) y Bernardo Llano (Departamento de Matemática, UAM, México).
Referencias
[1] HEDMAN, B; Clique Graphs of Time Graphs; JOURNAL OF COMBINATORIAL THEORY(1984), Series B 37, 270-278