Article ID Journal Published Year Pages File Type
4654762 European Journal of Combinatorics 2008 9 Pages PDF
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
, , ,