On the topology of simplicial complexes related to 3-connected and Hamiltonian graphs

摘要

Using techniques from Robin Forman's discrete Morse theory, we obtain information about the homology and homotopy type of some graph complexes. Specifically, we prove that the simplicial complex Delta(n)(3) of not 3-connected graphs on it vertices is homotopy equivalent to a wedge of (n - 3) (.) (n - 2)!/2 spheres of dimension 2n - 4, thereby verifying a conjecture by Babson, Bjorner, Linusson, Shareshian, and Welker. We also determine a basis for the corresponding nonzero homology group in the CW complex of 3-connected graphs. In addition, we show that the complex Gamma(n) of non-Hamiltonian graphs on it vertices is homotopy equivalent to a wedge of two complexes, one of the complexes being the complex Delta(n)(2) of not 2-connected graphs on it vertices. The homotopy type of Delta(n)(2) has been determined, independently, by the five authors listed above and by Turchin. While Gamma(n) and Delta(n)(2) are homotopy equivalent for small values on it, they are nonequivalent for n = 10. (C) 2003 Elsevier Inc. All rights reserved. [References: 13]