Equivariant collapses and the homotopy type of iterated clique graphs

The clique graph K ( G ) of a simple graph G is the intersection graph of its maximal complete subgraphs, and we define iterated clique graphs by K 0 ( G ) = G , K n + 1 ( G ) = K ( K n ( G ) ) . We say that two graphs are homotopy equivalent if their simplicial complexes of complete subgraphs are s...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2008-08, Vol.308 (15), p.3199-3207
Main Authors: LARRION, F, PIZANA, M. A, VILLARROEL-FLORES, R
Format: Article
Language:English
Subjects:
Algebraic topology
Applied sciences
Clique graphs
Computer science
control theory
systems
Exact sciences and technology
Graphs
Homotopy type
Information retrieval. Graph
Mathematics
Sciences and techniques of general use
Simple-homotopy
Theoretical computing
Topology. Manifolds and cell complexes. Global analysis and analysis on manifolds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The clique graph K ( G ) of a simple graph G is the intersection graph of its maximal complete subgraphs, and we define iterated clique graphs by K 0 ( G ) = G , K n + 1 ( G ) = K ( K n ( G ) ) . We say that two graphs are homotopy equivalent if their simplicial complexes of complete subgraphs are so. From known results, it can be easily inferred that K n ( G ) is homotopy equivalent to G for every n if G belongs to the class of clique-Helly graphs or to the class of dismantlable graphs. However, in both of these cases the collection of iterated clique graphs is finite up to isomorphism. In this paper, we show two infinite classes of clique-divergent graphs that satisfy G ≃ K n ( G ) for all n, moreover K n ( G ) and G are simple-homotopy equivalent. We provide some results on simple-homotopy type that are of independent interest.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2007.06.021