Grafos EPT en árboles de grado acotado.

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

Buenos Aires

Simposio; SIO 2014 - 12º Simposio Argentino de Investigación Operativa.; 2014

Una (h,s,t)-representación de un grafo G consiste de una colección de subárboles de un árbol T, donde cada subárbol corresponde a un vértice de G, tal que (i) el grado máximo de T es a lo sumo h, (ii) el grado máximo de los subárboles es a lo sumo s, (iii) existe una arista entre dos vértices en el grafo G si y sólo si los subárboles correspondientes tienen al menos t vértices en común en T. La clase de grafos que tiene una (h,s,t)-representación se denota [h,s,t]. Se sabe que $[infty,2,2]$=EPT, [3,2,2]=EPT Cordal y [4,2,2]= EPT Débilmente Cordal.Era una pregunta abierta ootnote{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 >3). Se sabe que si G está en la clase [h,2,2], entonces G no tiene ciclos sin cuerdas Cn para n > h, dado que existe una única EPT representación de Cn como una torta con n porciones. La recíproca es verdadera para h=3, dado que G debe ser crodal. La recíproca es falsa para h=4, dado que el complemento del  grafo C6 no tiene ciclos sin cuerdas de longitud mayor que 4 pero, sin embargo, no está en la clase [4,2,2]. Era una pregunta abierta saber si la recíproca es verdadera para h >4. Nosotras probamos que la misma es falsa para h >4. Esto es, encontramos una familia F(i,j,k), con i,j,k >0, tal que si i+j+k+2=h, entonces F(i,j,k) están en [h,2,2]-[h-1,2,2] y F(i,j,k) es libre de {Cn,  con n > h-1.