Reconocimiento y caracterización de cuadrados exactos de grafos.

Abstract: Para un grafo G=(V,E) se define su cuadrado exacto, G^{[#2]}, como el grafocon el mismo conjunto de vértices V en donde una arista uv está en el cuadrado exacto si y solo si u y v están a distancia 2 en el grafo original G. Se dice que G es una raíz (cuadrada) exacta de G^{[#2]}. Se mostrará una caracterización de los grafos que tienen raíz exacta, donde dicha caracterización permite fácilmente crear un algoritmo de reconocimiento en tiempo polinomial. Se mostrará que reconocer grafos que tienen una raíz exacta que es bipartita es un problema NP-completo. Se presentará una construcción de un grafo G en que existen árboles no isomorfos cuyo cuadrado exacto es G, lo que no ocurre para el caso de cuadrados normales. Y finalmente se presentará una caracterización de los grafos que tienen raíces exactas que son árboles, permitiendo un algoritmo de reconocimiento en tiempo polinomial.

Posted on May 29, 2023 in Seminario de Grafos, Seminars