Caracterización de los grafos local EPT en árboles de grado acotado.

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

Buenos Aires

Jornada; Primer encuentro de estudiantes de grado y posgrado en temas de Matemática Aplicada, de todas las universidades del grupo Montevideo (AUGM).; 2014

Instituto de Cálculo de la Facultad de Ciencias Exactas y Naturales de la UBA.

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 delos 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. Decimos que $\langle \mathcal{P},T \rangle$ es una \representación EPT local de G si es una representación EPT donde todos los cmainos 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]$ local, $G\notin [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]$, $G\notin [h-1,2,2]$ pero $G-v\in [h-1,2,2]$, para todo $v\in V(G)$, entonces $G\in [h,2,2]$ local.