Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654762 | European Journal of Combinatorics | 2008 | 9 Pages |
Abstract
To any finite poset P we associate two graphs which we denote by Ω(P) and â§(P). Several standard constructions can be seen as Ω(P) or â§(P) for suitable posets P, including the comparability graph of a poset, the clique graph of a graph and the 1-skeleton of a simplicial complex. We interpret graphs and posets as simplicial complexes using complete subgraphs and chains as simplices. Then we study and compare the homotopy types of Ω(P), â§(P) and P. As our main application we obtain a theorem, stronger than those previously known, giving sufficient conditions for a graph to be homotopy equivalent to its clique graph. We also introduce a new graph operator H that preserves clique-Hellyness and dismantlability and is such that H(G) is homotopy equivalent to both its clique graph and the graph G.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
F. Larrión, M.A. Pizaña, R. Villarroel-Flores,