zbMATH — the first resource for mathematics

Clique complexes and graph powers. (English) Zbl 1275.05041
Summary: We study the behaviour of clique complexes of graphs under the operation of taking graph powers. As an example we compute the clique complexes of powers of cycles, or, in other words, the independence complexes of circular complete graphs.

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76 Graph operations (line graphs, products, etc.)
05C38 Paths and cycles
Full Text: DOI
[1] J. A. Barmak, Star clusters in independence complexes of graphs, arxiv/1007.0418. · Zbl 1288.57004
[2] C. Bachoc, A. Pêcher and A. Thiéry, On the theta number of powers of cycle graphs, arxiv/1103.0444.
[3] A. Björner, Topological methods, in Handbook of Combinatorics, (R. Graham, M. Grötschel and L. Lovász, eds.), North-Holland, Amsterdam, 1995, pp. 1819–1872.
[4] R. Boulet, E. Fieux and B. Jouve, Simplicial simple-homotopy of flag complexes in terms of graphs, European Journal of Combinatorics 31 (2010), 161–176. · Zbl 1191.57002 · doi:10.1016/j.ejc.2009.05.003
[5] B. Braun, Independence complexes of stable Kneser graphs, Electronic Journal of Combinatorics 18 (2011), paper 118. · Zbl 1217.05174
[6] A. E. Brouwer, P. Duchet and A. Schrijver, Graphs whose neighbourhoods have no special cycles, Discrete Mathematics 47 (1983), 177–182. · Zbl 0546.05047 · doi:10.1016/0012-365X(83)90088-2
[7] J. Brown and R. Hoshino, Independence polynomials of circulants with an application to music, Discrete Mathematics 309 (2009), 2292–2304. · Zbl 1228.05178 · doi:10.1016/j.disc.2008.05.003
[8] A. Dochtermann, The universality of Hom complexes of graphs, Combinatorica 29 (2009), 433–448. · Zbl 1212.05263 · doi:10.1007/s00493-009-2376-7
[9] R. Forman, Morse theory for cell complexes, Advances in Mathematics 134 (1998), 90–145. · Zbl 0896.57023 · doi:10.1006/aima.1997.1650
[10] R. Forman, A user’s guide to discrete Morse theory, Séminaire Lotharingien de Combinatoire 48 (2002), article B48c. · Zbl 1048.57015
[11] R. Hoshino, Independence polynomials of circulant graphs, PhD. Thesis, Dalhouse University, 2007.
[12] D. Kozlov, Complexes of directed trees, Journal of Combinatorial Theory. Series A 88 (1999), 112–122. · Zbl 0934.05041 · doi:10.1006/jcta.1999.2984
[13] D. Kozlov, Combinatorial Algebraic Topology, Algorithms and Computation in Mathematics, Vol. 21, Springer-Verlag, Berlin-Heidelberg, 2008. · Zbl 1130.55001
[14] F. Larrión, M. A. Pizaña and R. Villarroel-Flores, The fundamental group of the clique graph, European Journal of Combinatorics 30 (2009), 288–294. · Zbl 1198.05092 · doi:10.1016/j.ejc.2007.12.006
[15] J. P. May, Weak equivalences and quasifibrations, in Groups of Self-equivalences and Related Topics (R. Piccinini, ed.), Lecture Notes in Mathematics, Vol. 1425, Springer-Verlag, Berlin, 1990, pp. 91–101.
[16] M. C. McCord, Singular homology groups and homotopy groups of finite topological spaces, Duke Mathematical Journal 33 (1966), 465–474. · Zbl 0142.21503 · doi:10.1215/S0012-7094-66-03352-7
[17] R. Motwani and M. Sudan, Computing roots of graphs is hard, Discrete Applied Mathematics 54 (1994), 81–88. · Zbl 0812.68103 · doi:10.1016/0166-218X(94)00023-9
[18] M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proceedings of the London Mathematical Society 88 (2004), 1–41. · Zbl 1045.05052 · doi:10.1112/S0024611503014412
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.