Change search
ReferencesLink to record
Permanent link

Direct link
Simplicial complexes of graphs and hypergraphs with a bounded covering number
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
2005 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 19, no 3, 633-650 p.Article in journal (Refereed) Published
Abstract [en]

For 1 <= p <= n- 1, define Cov(n,p) as the family of graphs on the vertex set {1,..., n} with a covering number of at most p ( equivalently, with an independence number of at least n = p). Since the underlying vertex set is fixed, we may identify each graph in Cov(n,p) with its edge set. In particular, we may view Cov(n,p) as a simplicial complex. For i >= - 1, we show that the rank of the ith homology group of Cov(n,p) is a linear combination, with coefficients being polynomials in n, of the ranks of the ith homology groups of Cov(p+2, p),..., Cov(2p+1,p). Our proof takes place in a more general setting where we consider complexes of hypergraphs. In addition, we show that the (2p - 1)- skeleton of Cov(n,p) is shellable, which implies that Cov(n,p) is (2p - 2)-connected. For p <= 3, we give a complete description of the homology groups of Cov(n,p).

Place, publisher, year, edition, pages
2005. Vol. 19, no 3, 633-650 p.
Keyword [en]
monotone graph property, simplicial homology, vertex cover, discrete Morse theory, discrete morse functions, connected graphs, decompositions, topology
URN: urn:nbn:se:kth:diva-15287ISI: 000234288300007ScopusID: 2-s2.0-33747155110OAI: diva2:333328
QC 20100525Available from: 2010-08-05 Created: 2010-08-05Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Jonsson, Jakob
By organisation
Mathematics (Div.)
In the same journal
SIAM Journal on Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link