Grafos cuyo cuadrado de línea es libre de P_k

Abstract

El grafo de línea de un grafo G, denotado L(G), es el grafo cuyos vértices son las aristas de G y tal que dos aristas de G son adyacentes en L(G) si y solo si comparten un extremo. El cuadrado 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. Denotamos por P_k al camino sin cuerdas con k vértices. Un grafo es libre de P_k si no contiene P_k como subgrafo inducido.