Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Complexes of graphs with bounded matching size
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).ORCID iD: 0000-0001-6339-2230
2008 (English)In: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192, Vol. 27, no 3, 331-349 p.Article in journal (Refereed) Published
Abstract [en]

For positive integers k, n, we investigate the simplicial complex NMk(n) of all graphs G on vertex set [n] such that every matching in G has size less than k. This complex (along with other associated cell complexes) is found to be homotopy equivalent to a wedge of spheres. The number and dimension of the spheres in the wedge are determined, and (partially conjectural) links to other combinatorially defined complexes are described. In addition we study for positive integers r, s and k the simplicial complex BNMk(r, s) of all bipartite graphs G on bipartition [r] boolean OR [(s) over bar] such that there is no matching of size k in G, and obtain results similar to those obtained for NMk(n).

Place, publisher, year, edition, pages
2008. Vol. 27, no 3, 331-349 p.
Keyword [en]
critical, trees of triangles, Gallai-Edmonds, morse-theory, topology
Identifiers
URN: urn:nbn:se:kth:diva-17447DOI: 10.1007/s10801-007-0092-1ISI: 000254849100006Scopus ID: 2-s2.0-42149171166OAI: oai:DiVA.org:kth-17447DiVA: diva2:335491
Note
QC 20100525Available from: 2010-08-05 Created: 2010-08-05 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Linusson, Svante

Search in DiVA

By author/editor
Linusson, Svante
By organisation
Mathematics (Div.)
In the same journal
Journal of Algebraic Combinatorics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 24 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf