Grafos cuyo cuadrado de línea es libre de P_k

SAFE, MARTÍN DARÍO ; VERGARA, MARTINA

Bahía Blanca

Congreso; XVII Congreso Dr. Antonio Monteiro; 2023

Universidad Nacional del Sur

El grafo de línea de un grafo G, denotado L(G), es el grafo cuyos vértices son las aristasde G y tal que dos aristas de G son adyacentes en L(G) si y solo si comparten un extremo. Elcuadrado de un grafo G, denotado G^2, es el grafo con los mismos vértices que G y tal que dos vértices son adyacentes si están unidos en G por un camino de longitud a lo sumo 2. Denotamospor P_k al camino sin cuerdas con k vértices. Un grafo es libre de P_k si no contiene P_k comosubgrafo inducido. Dos aristas se dicen independientes si no comparten extremos ni son ambas incidentes a una arista en común. Un matching inducido es un conjunto de aristas independientes dosa dos. El problema del MATCHING INDUCIDO MÁXIMO consiste en hallar un matching inducido de máxima cardinalidad. El problema del CONJUNTO INDEPENDIENTE MÁXIMO consiste en hallar un conjunto de vértices no adyacentes dos a dos de máxima cardinalidad. Claramente, resolver el problema de MATCHING INDUCIDO MÁXIMO en un grafo G es equivalente a resolver el problema de CONJUNTO INDEPENDIENTE MÁXIMO en L(G)^2. Este hecho implica que el problema de MATCHING INDUCIDO MÁXIMO puede resolverse en tiempo polinomial (resp. cuasipolinomial) para la clase de todos los grafos G tales que L(G)^2 ∈ H , para cada clase H de grafos en la cual el problema de CONJUNTO INDEPENDIENTE MÁXIMO puede resolverse en tiempo polinomial (resp. cuasipolinomial). Por ejemplo, una clase de grafos H en la cual el problema de CONJUNTO INDEPENDIENTE MÁXIMO puede resolverse en tiempo polinomial es la clase de los grafos cordales. Luego, el problema del MATCHING INDUCIDO MÁXIMO puede resolverse en tiempo polinomial en la clase de los grafos G tales que L(G)^2 es cordal. Una caracterización de la clase de tales grafos G, por subgrafos inducidos prohibidos minimales, fue dada por Scheidweiler y Wiederrecht. Una clase de grafos H en la cual el problema de CONJUNTO INDEPENDIENTE MÁXIMO puede resolverse en tiempo cuasipolinomial es la clase de los grafos libres de Pk, para cada k. En consecuencia, si G_k es la clase de los grafos G tales que L(G)^2 es libre de P_k entonces el problema de MATCHING INDUCIDO MÁXIMO puede resolverse en tiempo cuasipolinomial en G_k, cualquiera sea k. Hatzel y Wiederrecht estudiaron el problema de caracterizar la clase G_k por subgrafos inducidos prohibidos. Sin embargo, su caracterización no es por subgrafos inducidos prohibidos minimales, pues algunos de los subgrafos prohibidos contienen a otros como subgrafos inducidos propios.En este trabajo, obtenemos una caracterización por subgrafos inducidos prohibidos minimales de la clase Gk, para cada k. Cada familia de subgrafos inducidos prohibidos minimales quedacaracterizada mediante un conjunto de cadenas aceptadas por un autómata finito determinista.