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

6 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

Funding

Funders	Funder number
Directorate for Computer and Information Science and Engineering	0097278

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 - https://www.scopus.com/pages/publications/43449089191

UR - https://www.scopus.com/pages/publications/43449089191#tab=citedBy

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

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this