On the number of minimal transversals in 3-uniform hypergraphs

Zbigniew Lonc; Mirosław Truszczyński

doi:10.1016/j.disc.2007.07.024

On the number of minimal transversals in 3-uniform hypergraphs

Zbigniew Lonc, Mirosław Truszczyński

Computer Science

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

We prove that the number of minimal transversals (and also the number of maximal independent sets) in a 3-uniform hypergraph with n vertices is at most cⁿ, where c ≈ 1.6702. The best known lower bound for this number, due to Tomescu, is adⁿ, where d = 10^{1 / 5} ≈ 1.5849 and a is a constant.

Original language	English
Pages (from-to)	3668-3687
Number of pages	20
Journal	Discrete Mathematics
Volume	308
Issue number	16
DOIs	https://doi.org/10.1016/j.disc.2007.07.024
State	Published - Aug 28 2008

Keywords

Maximal independent set
Minimal transversal
Uniform hypergraph

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2007.07.024

Cite this

@article{c758cc20fe404de9bd2e3ef4188d6c1a,

title = "On the number of minimal transversals in 3-uniform hypergraphs",

abstract = "We prove that the number of minimal transversals (and also the number of maximal independent sets) in a 3-uniform hypergraph with n vertices is at most cn, where c ≈ 1.6702. The best known lower bound for this number, due to Tomescu, is adn, where d = 101 / 5 ≈ 1.5849 and a is a constant.",

keywords = "Maximal independent set, Minimal transversal, Uniform hypergraph",

author = "Zbigniew Lonc and Miros{\l}aw Truszczy{\'n}ski",

year = "2008",

month = aug,

day = "28",

doi = "10.1016/j.disc.2007.07.024",

language = "English",

volume = "308",

pages = "3668--3687",

number = "16",

}

TY - JOUR

T1 - On the number of minimal transversals in 3-uniform hypergraphs

AU - Lonc, Zbigniew

AU - Truszczyński, Mirosław

PY - 2008/8/28

Y1 - 2008/8/28

N2 - We prove that the number of minimal transversals (and also the number of maximal independent sets) in a 3-uniform hypergraph with n vertices is at most cn, where c ≈ 1.6702. The best known lower bound for this number, due to Tomescu, is adn, where d = 101 / 5 ≈ 1.5849 and a is a constant.

AB - We prove that the number of minimal transversals (and also the number of maximal independent sets) in a 3-uniform hypergraph with n vertices is at most cn, where c ≈ 1.6702. The best known lower bound for this number, due to Tomescu, is adn, where d = 101 / 5 ≈ 1.5849 and a is a constant.

KW - Maximal independent set

KW - Minimal transversal

KW - Uniform hypergraph

UR - http://www.scopus.com/inward/record.url?scp=43449089191&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=43449089191&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2007.07.024

DO - 10.1016/j.disc.2007.07.024

M3 - Article

AN - SCOPUS:43449089191

SN - 0012-365X

VL - 308

SP - 3668

EP - 3687

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 16

ER -

On the number of minimal transversals in 3-uniform hypergraphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this