Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649006 | Discrete Mathematics | 2010 | 8 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Kazuhiro Kawamura,