Domination numbers and noncover complexes of hypergraphs

DOI10.1016/J.JCTA.2021.105408MaRDI QIDQ2229171zbMATH OpenOpenAlexWikidataFDO

Authors Jinha Kim, Min-Ki Kim

Publication date 22 February 2021

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.01850

zbMATH Keywords

homological connectivityhypergraph domination numbersindependence complexesLeray numbersnoncover complexes

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial aspects of simplicial complexes (05E45)

Abstract: Let $mathcalH$ be a hypergraph on a finite set $V$. A {em cover} of $mathcalH$ is a set of vertices that meets all edges of $mathcalH$. If $W$ is not a cover of $mathcalH$, then $W$ is said to be a {em noncover} of $mathcalH$. The {em noncover complex} of $mathcalH$ is the abstract simplicial complex whose faces are the noncovers of $mathcalH$. In this paper, we study homological properties of noncover complexes of hypergraphs. In particular, we obtain an upper bound on their Leray numbers. The bound is in terms of hypergraph domination numbers. Also, our proof idea is applied to compute the homotopy type of the noncover complexes of certain uniform hypergraphs, called {em tight paths} and {em tight cycles}. This extends to hypergraphs known results on graphs.

Recommendations

• Noncover complexes, independence complexes, and domination numbers of hypergraphs
• Dominance complexes and vertex cover numbers of graphs
• Simplicial Complexes of Graphs and Hypergraphs with a Bounded Covering Number
• Collapsibility of non-cover complexes of graphs
• Domination numbers and homology

Cites work

• A geometric Hall-type theorem
• A topological colorful Helly theorem
• Bounding the projective dimension of a squarefree monomial ideal via domination in clutters
• Collapsibility of non-cover complexes of graphs
• Complexes of directed trees
• Domination in hypergraphs
• Domination numbers and homology
• Enumeration of \({\mathbb{Q}}\)-acyclic simplicial complexes
• Further applications of clutter domination parameters to projective dimension
• Hall's theorem for hypergraphs
• scientific article; zbMATH DE number 3545783 (Why is no real title available?)
• Independence complexes and incidence graphs
• Intersections of Leray complexes and regularity of monomial ideals
• Linear Diophantine equations and local cohomology
• Noncover complexes, independence complexes, and domination numbers of hypergraphs
• Note: Combinatorial Alexander duality -- a short and elementary proof
• Projective dimension, graph domination parameters, and independence complex homology
• Star clusters in independence complexes of graphs
• The clique complex and hypergraph matching
• Total transversals and total domination in uniform hypergraphs
• Triangulated spheres and colored cliques

Cited in

(10)

• Noncover complexes, independence complexes, and domination numbers of hypergraphs
• Collapsibility of non-cover complexes of graphs
• Non-regular graph coverings and lifting the hyperelliptic involution
• A characterization of hypergraphs with large domination number
• Haar null and non-dominating sets
• scientific article; zbMATH DE number 5917555 (Why is no real title available?)
• scientific article; zbMATH DE number 7456252 (Why is no real title available?)
• Simplicial Complexes of Graphs and Hypergraphs with a Bounded Covering Number
• Dominance complexes and vertex cover numbers of graphs
• Application of superhypergraphs-based domination number in real world

This page was built for publication: Domination numbers and noncover complexes of hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2229171)