Access the full text.
Sign up today, get DeepDyve free for 14 days.
Loading next page...
/lp/springer-journals/dominance-complexes-and-vertex-cover-numbers-of-graphs-6kTzxsfGSv
References (31)
-
M Adamaszek (2012)
1031J. Comb. Theory Ser. A, 119
-
JA Barmak (2013)
Star clusters in independence complexes of graphsAdv. Math., 241
-
R. Ehrenborg, G. Hetyei (2006)
The topology of the independence complexEur. J. Comb., 27
-
J. Matoušek (2007)
Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry -
E. Babson, D. Kozlov (2004)
Proof of the Lovász conjectureAnnals of Mathematics, 165
-
H. Erdin (2004)
Characteristic Classes -
E Babson (2007)
965Ann. Math., 165
-
J. Jonsson (2011)
On the Topology of Independence Complexes of Triangle-Free Graphs -
(2008)
Combinatorial algebraic topology, Springer, Berlin, Algorithms and Computation -
A. Dochtermann (2018)
Exposed circuits, linear quotients, and chordal cluttersJ. Comb. Theory, Ser. A, 177
-
Russ Woodroofe (2009)
Chordal and Sequentially Cohen-Macaulay CluttersElectron. J. Comb., 18
-
Demet Taylan (2015)
Matching Trees for Simplicial Complexes and Homotopy Type of Devoid Complexes of GraphsOrder, 33
-
K. Kawamura (2010)
Independence complexes of chordal graphsDiscret. Math., 310
-
Stefan Friedl (2020)
Algebraic topologyGraduate Studies in Mathematics
-
Michal Adamaszek (2011)
Splittings of independence complexes and the powers of cyclesJ. Comb. Theory, Ser. A, 119
-
(2011)
Department of Mathematical Sciences, University of the Ryukyus, Nishihara-cho, Okinawa 903-0213 -
D. Kozlov (1999)
Complexes of Directed TreesJ. Comb. Theory, Ser. A, 88
-
K. Brown, Hsiao-Lan Liu (1982)
Graduate Texts in Mathematics -
A Dochtermann (2021)
Exposed circuits, linear quotients, and chordal cluttersJ. Comb. Ser. Theory A, 177
-
U. Nagel, V. Reiner (2007)
Betti Numbers of Monomial Ideals and Shifted Skew ShapesElectron. J. Comb., 16
-
M. Marietti, D. Testa (2007)
Cores of Simplicial ComplexesDiscrete & Computational Geometry, 40
-
M. Marietti, D. Testa (2008)
A Uniform Approach to Complexes arising from ForestsElectron. J. Comb., 15
-
R. Meshulam (2003)
Domination numbers and homologyJ. Comb. Theory, Ser. A, 102
-
Ezra Miller, B. Sturmfels (2004)
Combinatorial Commutative Algebra -
J. Matoušek (2003)
Using The Borsuk-Ulam Theorem -
JA Barmak (2013)
33Adv. Math., 241
-
J. Barmak (2010)
Star clusters in independence complexes of graphsarXiv: Combinatorics
-
Alexander Engström (2005)
Complexes of directed trees and independence complexesDiscret. Math., 309
-
Priyavrat Deshpande, Anurag Singh (2020)
Higher Independence Complexes of graphs and their homotopy typesarXiv: Algebraic Topology
-
S. Tsukuda (2017)
Independence complexes and incidence graphsContributions Discret. Math., 12
-
Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations
- Publisher
- Springer Journals
- Copyright
- Copyright © The Author(s), under exclusive licence to Springer Nature Switzerland AG 2022. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
- ISSN
- 2367-1726
- eISSN
- 2367-1734
- DOI
- 10.1007/s41468-022-00109-2
- Publisher site
- See Article on Publisher Site
Abstract
The dominance complex D(G) of a simple graph G=(V,E)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$G = (V,E)$$\end{document} is the simplicial complex consisting of the subsets of V whose complements are dominating. We show that the connectivity of D(G) plus 2 is a lower bound for the vertex cover number τ(G)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\tau (G)$$\end{document} of G.
Journal
Journal of Applied and Computational Topology – Springer Journals
Published: Jun 1, 2023
Keywords: Dominance complex; Independence complex; Alexander dual; Vertex cover number; Primary 05C15; Secondary 55U10