On the homotopy type of the clique graph
If G is a graph, its clique graph K(G) is the intersection graph of all its (maximal) cliques. The complex G<FONT FACE=Symbol></FONT> of a graph G is the simplicial complex whose simplexes are the vertex sets of the complete subgraphs of G. Here we study a sufficient condition for G<FONT FACE=Symbol></FONT> and K(G)<FONT FACE=Symbol></FONT> to be homotopic. Applying this result to Whitney triangulations of surfaces, we construct an infinite family of examples which solve in the affirmative Prisner's open problem 1 in Graph Dynamics (Longman, Harlow, 1995): Are there finite connected graphs G that are periodic under K and where the second modulo 2 Betti number is greater than 0?
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Digital revista |
| Language: | English |
| Published: |
Sociedade Brasileira de Computação
2001
|
| Online Access: | http://old.scielo.br/scielo.php?script=sci_arttext&pid=S0104-65002001000200010 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|