Sesión Matemática DiscretaSobre la dominación de caminos en grafos orientados
María Pía Mazzoleni
Universidad Nacional La Plata, CMaLP, CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Un grafo orientado $D$ está formado por un par $ (V (D), A(D))$: siendo $V (D)$ es el conjunto (finito) de vértices de $D$ y $A(D)$ el conjunto de pares ordenados de vértices distintos de $D$, llamados arcos, que se notan por $uv$. Dos vértices son adyacentes si existe un arco que los una. Un arco $uv$ es una arista orientada de $u$ hacia $v$. Los vértices $u$ y $v$ son los extremos de ese arco. El vértice $u$ se llama cola y $v$ se llama cabeza.
En este trabajo tratamos con el problema de dominación de caminos en grafos orientados. Mostramos que la noción de dominación entre distintos tipos de caminos tiene un rol fundamental a la hora de caracterizar a las clases de grafos orientados.
Un recorrido orientado en $D$ es una secuencia alternada $W = x_1, a_1, x_2, a_2, x_3,..., x_{k−1}, a_{k−1}, x_k$ de vértices $x_i$ y arcos $a_j$ de D tal que $x_i$ y $x_{i+1}$ son la cola y la cabeza de $a_i$, respect.
Si los vértices del recorrido orientado $W$ son distintos, decimos que $W$ es un camino orientado. Si los vértices $x_1, x_2,..., x_{k−1}$ son distintos, $k\geq 3$ y $x_1 = x_k$, $W$ es un ciclo orientado notado $\overrightarrow{C_k}$.
En todos estos casos la longitud es su número de arcos.
El $(x,y)$-camino orientado más corto (más largo) en $D$ es un $(x,y)$-camino orientado de longitud mínima (máxima) en $D$.
Un $(x,y)$-camino orientado inducido es un $(x,y)$-camino orientado $x = x_1, x_2,..., x_k = y$ tal que los únicos arcos son $x_ix_{i+1}$ para $i\in \{1, . . . , k-1\}$.
Sean $W$ y $W '$ recorridos orientados con los mismos no adyacentes vértices extremos. Decimos que $W$ domina a $W'$ si todo vértice interno de $W'$ es adyacente a algún vértice interno de $W$ o pertenece a $W$.
Notación: Sean $x$ e $y$ vértices no adyacentes de $D$.
$\overrightarrow{SDP}(x,y)$$=\{W: \hbox{W es un (x,y)-camino orientado más corto} \}$;
$\overrightarrow{IDP}(x,y)$$=\{W: \hbox{W es un (x,y)-camino orientado inducido}\}$.
$\overrightarrow{W}(x,y)$$=\{W: \hbox{W es un (x,y)-recorrido} \}$;
$\overleftarrow{SDP}(x,y)$$=\overrightarrow{SDP}(y,x)$;
$\overleftarrow{IDP}(x,y)$$=\overrightarrow{IDP}(y,x)$;
$\overleftarrow{W}(x,y)$$=\overrightarrow{W}(y,x)$.
Definición: Sean $A, B \in \{ \overrightarrow{SDP},\overleftarrow{SDP},\overrightarrow{IDP},\overleftarrow{IDP}, \overrightarrow{W},\overleftarrow{W}\}$. La clase $\textbf{A}/\textbf{B}$ está formada por los grafos orientados $D$ tal que: para todo par de vértices no adyacentes $x$ e $y$ de $D$, se tiene que: todo $W\in \textbf{A}(x,y)$ domina a todo $W' \in \textbf{B}(x,y)$, es decir, $W \in \textbf{A}(x,y)$ y $W' \in \textbf{B}(x,y)$ implica que $W$ domina a $W'$.
En este trabajo, damos Teoremas de caracterización de las clases $\overrightarrow{IDP}/\overleftarrow{IDP}$, $\overrightarrow{SDP}/\overleftarrow{IDP}$, $\overrightarrow{W}/\overleftarrow{IDP}$ por subgrafos inducidos prohibidos. Y de otras clases que salen directamente por simetría. Lo cual demuestra que dichas clases son hereditarias. Observamos que no todas las clases son hereditarias.
Trabajo en conjunto con: Noemí Gudiño (Universidad Nacional de La Plata, CMaLP, Argentina). y Silvia B. Tondato (Universidad Nacional de La Plata, CMaLP, Argentina).