On the Homotopy Type of the Iterated Clique Graphs of Low Degree.

To any simple graph G , the clique graph operator K assigns the graph K (G) , which is the intersection graph of the maximal complete subgraphs of G . The iterated clique graphs are defined by K 0 (G) = G and K n (G) = K (K n - 1 (G)) for n ≥ 1 . We associate topological concepts to graphs by means of the simplicial complex Cl (G) of complete subgraphs of G . Hence, we say that the graphs G 1 and G 2 are homotopic whenever Cl (G 1) and Cl (G 2) are. A graph G such that K n (G) ≃ G for all n ≥ 1 is called K -homotopy permanent. A graph is Helly if the collection of maximal complete subgraphs of G has the Helly property. Let G be a Helly graph. Escalante (1973) proved that K (G) is Helly, and Prisner (1992) proved that G ≃ K (G) , and so Helly graphs are K -homotopy permanent. We conjecture that if a graph G satisfies that K m (G) is Helly for some m ≥ 1 , then G is K -homotopy permanent. If a connected graph has maximum degree at most four and is different from the octahedral graph, we say that it is a low degree graph. It was recently proven that all low-degree graphs G satisfy that K 2 (G) is Helly. In this paper, we show that all low-degree graphs have the homotopy type of a wedge or circumferences, and that they are K -homotopy permanent. [ABSTRACT FROM AUTHOR]