On the topology of simplicial complexes related to 3-connected and Hamiltonian graphs
2003 (English)In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 104, no 1, 169-199 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
2003. Vol. 104, no 1, 169-199 p.
monotone graph property, discrete morse theory, topological combinatorics, 3-connected graph, Hamiltonian graph, connected graphs, morse-theory
IdentifiersURN: urn:nbn:se:kth:diva-22955ISI: 000186552200011OAI: oai:DiVA.org:kth-22955DiVA: diva2:341653
QC 201005252010-08-102010-08-10Bibliographically approved