Sesión Matemática Discreta

Diciembre 13, 12:20 ~ 12:40

Sobre la Existencia de Grafos Clique-Helly Críticos

RAVENNA, Gabriela Susana

Un \textbf{completo} en un grafo $G$ es un subconjunto de vértices mutuamente adyacentes. Un \textbf{clique} es un completo maximal con respecto a la inclusion. La familia de cliques de $G$ se denota $\mathcal{C}(G)$. Cuando $\mathcal{C}(G)$ satisface la propiedad de Helly (toda subfamilia mutuamente intersectante tiene intersección total no vacía) se dice que $G$ es \textbf{clique-Helly}. Dourado, Protti y Szwarcfiter conjecturaron en \cite{jaime} que todo grafo clique-Helly $G$ contiene un vertice $v$ tal que $G-v$ es clique-Helly. El \textbf{grafo clique} $K(G)$ de $G$ es el grafo intersección de $\mathcal{C}(G)$: los vertices de $K(G)$ son los cliques de $G$ y dos vértices son adyacentes si los correspondientes cliques de $G$ tienen intersección no vacía. El \textbf{producto tensorial} entre dos grafos $G$ y $H$ es el grafo $G\times H$ con $V(G\times H)=V(G) \times V(H)$ y una arista entre vértices $(i,j)$, $(i', j')$ si $i, i'$ son adyacentes en $G$ y $j,j'$ son adyacentes en $H$. En este trabajo probamos que la conjetura de Dourado, Protti y Szwarcfiter no es válida. El contraejemplo surge del grafo clique del grafo producto tensorial del icosaedro $I$ y un completo de 3 vértices $K_3$, es decir $K(I \times K_3)$. \begin{thebibliography}{999} \bibitem{jaime} M.C. Dourado, F. Protti, J.L. Szwarcfiter, \emph{Computational Aspects of the Helly Property: a Survey}, Journal of the Brazilian Computer Society {\bf 12}, Issue 1, (2006), 7--33. \end{thebibliography}

Autores: RAVENNA, Gabriela Susana / Alcón, Liliana / Pizaña, Miguel .