×

On the homotopy type of the iterated clique graphs of low degree. (English) Zbl 1539.05130

Summary: 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\geq 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 \(n\geq 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. F. Escalante [Abh. Math. Semin. Univ. Hamb. 39, 58–68 (1973; Zbl 0266.05116)] proved that \(K(G)\) is Helly, and E. Prisner [Discrete Math. 103, No. 2, 199–207 (1992; Zbl 0766.05096)] proved that \(G\simeq 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\geq 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.

MSC:

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

References:

[1] Adamaszek, M.; Adams, H.; Frick, F.; Peterson, C.; Previte-Johnson, C., Nerve complexes of circular arcs, Discrete Comput. Geom., 56, 2, 251-273, 2016 · Zbl 1354.05149 · doi:10.1007/s00454-016-9803-5
[2] Bandelt, H.; Prisner, E., Clique graphs and Helly graphs, J. Combin. Theory Ser. B, 51, 1, 34-45, 1991 · Zbl 0726.05060 · doi:10.1016/0095-8956(91)90004-4
[3] Björner, A., Topological methods, Handbook of combinatorics, 1819-1872, 1995, Amsterdam: Elsevier, Amsterdam · Zbl 0851.52016
[4] Boulet, R.; Fieux, E.; Jouve, B., Simplicial simple-homotopy of flag complexes in terms of graphs, Eur. J. Combin., 31, 1, 161-176, 2010 · Zbl 1191.57002 · doi:10.1016/j.ejc.2009.05.003
[5] Escalante, F., Über iterierte Clique-Graphen, Abh. Math. Sem. Univ. Hamburg, 39, 59-68, 1973 · Zbl 0266.05116 · doi:10.1007/BF02992818
[6] Frías-Armenta, ME; Neumann-Lara, V.; Pizaña, MA, Dismantlings and iterated clique graphs, Discrete Math., 282, 1-3, 263-265, 2004 · Zbl 1042.05070 · doi:10.1016/j.disc.2003.12.011
[7] F. Harary. Graph theory. Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. · Zbl 0182.57702
[8] Hatcher, A., Algebraic topology, 2002, Cambridge: Cambridge University Press, Cambridge · Zbl 1044.55001
[9] Larrión, F.; Pizaña, MA; Villarroel-Flores, R., Discrete Morse theory and the homotopy type of clique graphs, Ann. Comb., 17, 4, 743-754, 2013 · Zbl 1284.05228 · doi:10.1007/s00026-013-0204-7
[10] Larrión, F.; Pizaña, MA; Villarroel-Flores, R., Contractibility and the clique graph operator, Discrete Math., 308, 16, 3461-3469, 2008 · Zbl 1171.05388 · doi:10.1016/j.disc.2007.07.004
[11] Larrión, F.; Pizaña, MA; Villarroel-Flores, R., Equivariant collapses and the homotopy type of iterated clique graphs, Discrete Math., 308, 15, 3199-3207, 2008 · Zbl 1171.05387 · doi:10.1016/j.disc.2007.06.021
[12] Larrión, F.; Pizaña, MA; Villarroel-Flores, R., Posets, clique graphs and their homotopy type, Eur. J. Combin., 29, 1, 334-342, 2008 · Zbl 1127.05073 · doi:10.1016/j.ejc.2006.04.012
[13] Larrión, F.; Pizaña, MA; Villarroel-Flores, R., The clique operator on matching and chessboard graphs, Discrete Math., 309, 1, 85-93, 2009 · Zbl 1207.05158 · doi:10.1016/j.disc.2007.12.047
[14] Larrión, F.; Neumann-Lara, V.; Pizaña, MA, On the homotopy type of the clique graph, J. Brazil. Comput. Soc., 7, 69-73, 2001 · doi:10.1590/S0104-65002001000200010
[15] V. Neumann-Lara. On clique-divergent graphs. Problèmes combinatoires et théorie des graphes, Orsay 1976, Colloq. int. CNRS No. 260, 313-315 (1978)., 1978. · Zbl 0413.05058
[16] Prisner, E., Convergence of iterated clique graphs, Discrete Math., 103, 2, 199-207, 1992 · Zbl 0766.05096 · doi:10.1016/0012-365X(92)90270-P
[17] Villarroel-Flores, Rafael, On the clique behavior of graphs of low degree, Boletín de la Sociedad Matemática Mexicana, 28, 2, 1-11, 2022 · Zbl 1496.05152 · doi:10.1007/s40590-022-00438-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.