IJPAM: Volume 94, No. 3 (2014)

EQUIVALENCE OF TWO WIDELY RESEARCHED
PROBLEMS IN HYPERGRAPH THEORY

R. Dharmarajan$^1$, K. Kannan$^2$
$^{1,2}$Department of Mathematics
SASTRA University
Thanjavur, Tamilnadu State, INDIA


Abstract. The problems of enumerating (i) all the minimal transversals and (ii) all the minimal dominating sets, in a given hypergraph, have received a lot of attention because of their applications in Computer Science. This article explores the possibilities of these two problems being solution-wise equivalent - that is, each solution to one of them being a solution to the other - in the domain of Sperner hypergraphs, culminating in identifying the only class of such hypergraphs in which the equivalence holds.

Received: January 2, 2014

AMS Subject Classification: 05C65

Key Words and Phrases: hypergraph, hyperedge, Sperner hypergraphs, trim hypergraph, transversal, dominating set

Download paper from here.



DOI: 10.12732/ijpam.v94i3.6 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2014
Volume: 94
Issue: 3
Pages: 373 - 377

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).