Nuevos resultados sobre los grafos EPT.

LILIANA ALCÓN; MARISA GUTIERREZ; MARÍA PÍA MAZZOLENI

San Luis

Congreso; LXIII Reunión Anual de Comunicaciones Científicas. 2014; 2014

Un grafo G es llamado un grafo EPT si es el grafo arista intersección de una familia de caminos en un árbol. Una representación EPT de G es un par $\langle \mathcal{P},T \rangle$ donde $\mathcal{P}$ es una familia $(P_v)_{v\in V(G)}$ de subcaminos de un árbol huésped T satisfaciendo que dos vértices v y v' de G son adyacentes si y sólo si $P_v$ y $P_{v'}$ tienen al menos dos vértices (una arista) en común. Cuando el grado máximo del árbol huésped T es h, la representación EPT de G es llamada una (h,2,2)-representación de G. La clase de grafos que admite una (h,2,2)-representación se denota [h,2,2]. Notar que la clase de los grafos EPT es la unión de las clases [h,2,2] para $h\geq2$. Golumbic y Jamison probaron que reconocer a los grafos EPT es un problema NP-completo.  Sea C un clique de G. Un vértice v de G es un satélite de C si $B_v=N(v) \cap C$ es un subconjunto propio no vacío de C. $B_v$ es llamada la base de v y ésta se dice minimal si ninguna otra base de un satélite de C está propiamente contenida en $B_v$. Probamos el siguiente teorema:Teorema: Sea $G\in EPT$ y sea C un clique de G. Si $w\in C$ entonces w pertenece a lo sumo a dos bases minimales diferentes de satélites no adyacentes de C.  Caracterizamos a los grafos minimales que no satisfacen la condición anterior y, como una consecuencia, presentamos una nueva familia finita de subgrafos inducidos prohibidos minimales para la clase EPT.  Era una pregunta abierta\footnote{Equivalences and the complete hierarchy of intersection graphs of paths in a tree, Discrete Applied Mathematics. 156 (2008) 3203-3215.} conocer la relación entre el grado máximo h del árbol huésped y la longitud n del mayor ciclo sin cuerdas ($n\geq 4$). Se sabe que si $G\in [h,2,2]$, entonces G no tiene ciclos sin cuerdas $C_n$ para $n\geq h+1$. La recíproca es verdadera para h=3 y falsa para h=4. Era una pregunta abierta saber si la recíproca es verdadera para $h\geq 5$. Nosotras probamos que es falsa para $h\geq 5$. Encontramos una familia $F_{i,j,k}$, con $i,j,k\geq 1$, tal que si i+j+k+2=h, entonces $F_{i,j,k}\in [h,2,2]-[h-1,2,2]$ y $F_{i,j,k}$ es libre de $\{C_{n}, n\geq h\}$.  Decimos que $\langle \mathcal{P},T \rangle$ es una representación EPT local de G si es una representación EPT donde todos los caminos de $\mathcal{P}$ tienen un vértice en común en T. Diremos que G es un grafo EPT local si tiene una representación EPT local. Sea $h\geq 5$, G pertenece a la clase [h,2,2] local si y sólo si G tiene una representación EPT local en un árbol huésped T con grado máximo h.  En este trabajo, estudiamos la estructura local de los caminos que pasan a través de un vértice dado del árbol huésped, el cual tiene grado máximo h. Mostramos que estos grafos que son localmente EPT son equivalentes a ciertos grafos de líneas.Teorema: Sea $h\geq 5$. $G\in [h,2,2] - [h-1,2,2]$ y G sin vértices dominados adyacentes si y sólo si G=L(H) con H un grafo tal que:(i) |V(H)|=h; (ii) H no tiene vértices de grado 1; (iii) H es simple; (iv) H no tiene vértices dominados adyacentes; (v) H tiene un ciclo $C_n$, con $4 \leq n\leq h$, y todo vértice de H-C_n está en algún camino entre dos vértices diferentes de $C_n$.Conjetura: Sea $h\geq 5$. Si $G\in [h,2,2] - [h-1,2,2]$ minimal entonces $G\in [h,2,2]$local.