On the homotopy type of the iterated clique graphs of low degree

DOI10.1007/S00026-023-00665-ZarXiv2205.09237OpenAlexW4387496093MaRDI QIDQ6399546FDOQ6399546

Authors: Mauricio Islas-Gómez, Rafael Villarroel-Flores 

Publication date: 18 May 2022

Abstract: 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 (ngeq 1). We associate topological concepts to graphs by means of the simplicial complex (mathrm{Cl}(G)) of complete subgraphs of (G). Hence we say that the graphs (G_{1}) and (G_{2}) are homotopic whenever (mathrm{Cl}(G_{1})) and (mathrm{Cl}(G_{2})) are. A graph (G) such that (K^{n}(G)simeq G) for all (ngeq1) is called emph{(K)-homotopy permanent}. A graph is emph{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 (Gsimeq 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 (mgeq1), 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 emph{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.

Full work available at URL: https://doi.org/10.1007/s00026-023-00665-z

Recommendations

• Equivariant collapses and the homotopy type of iterated clique graphs
• On the clique behavior of graphs of low degree
• Clique graphs and Helly graphs
• Posets, clique graphs and their homotopy type
• On clique convergent graphs

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Combinatorial aspects of simplicial complexes (05E45)

This page was built for publication: On the homotopy type of the iterated clique graphs of low degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6399546)