A note on improved upper bounds on the transversal number of hypergraphs

Michael A. Henning, Nader Jafari Rad

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

A subset T of vertices in a hypergraph H is a transversal if T has a nonempty intersection with every edge of H. The transversal number of H is the minimum size of a transversal in H. A subset S of vertices in a graph G with no isolated vertex, is a total dominating set if every vertex of G is adjacent to a vertex of S. The minimum cardinality of a total dominating set in G is the total domination number of G. In this paper, we obtain a new (improved) probabilistic upper bound for the transversal number of a hypergraph, and a new (improved) probabilistic upper bound for the total domination number of a graph.

Original languageEnglish
Article number1950004
JournalDiscrete Mathematics, Algorithms and Applications
Volume11
Issue number1
DOIs
Publication statusPublished - 1 Feb 2019

Keywords

  • Hypergraph
  • independence number
  • total domination
  • transversals

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'A note on improved upper bounds on the transversal number of hypergraphs'. Together they form a unique fingerprint.

Cite this