Article ID Journal Published Year Pages File Type
4649006 Discrete Mathematics 2010 8 Pages PDF
Abstract

We show that the independence complex I(G) of an arbitrary chordal graph GG is either contractible or is homotopy equivalent to the finite wedge of spheres of dimension at least the domination number of GG minus 1. Also it is shown that every finite wedge of spheres (as well as a singleton) is realized as the homotopy type of the independence complex of a chordal graph. A combinatorial consequence is a verification of a conjecture due to Aharoni et al. [2, Conjecture 2.4] for chordal graphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,