The minimum number of e-vertex-covers among hypergraphs with e edges of given ranks

F. H. Chang*, Hung-Lin Fu, F. K. Hwang, B. C. Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We study the problem that among all hypergraphs with e edges of ranks l1, ..., le and v vertices, which hypergraph has the least number of vertex-covers of size e. The problem is very difficult and we only get some partial answers. We show an application of our results to improve the error-tolerance of a pooling design proposed in the literature.

Original languageEnglish
Pages (from-to)164-169
Number of pages6
JournalDiscrete Applied Mathematics
Volume157
Issue number1
DOIs
StatePublished - 6 Jan 2009

Keywords

  • Hypergraph
  • Pooling design
  • Vertex-cover

Fingerprint

Dive into the research topics of 'The minimum number of e-vertex-covers among hypergraphs with e edges of given ranks'. Together they form a unique fingerprint.

Cite this