On covering a product of sets with products of their subsets

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Suppose that S1,...,SN are collections of subsets of X1,...,XN, respectively, such that ni subsets belonging to Si, and no fewer, cover Xi for all i. the main result of this paper is that to cover X1 x...x XN requires no fewer than σNi=1 (ni-1) + 1 and no more than ΠNi=1ni subsets of the form A1 x...x AN, where Ai∈S1 for all i. Moreo ver, these bounds cannot be improved. Identical bounds for the spanning number of a normal product of graphs are also obtained.

Original languageEnglish (US)
Pages (from-to)373-380
Number of pages8
JournalDiscrete Mathematics
Volume5
Issue number4
DOIs
StatePublished - Aug 1973
Externally publishedYes

Bibliographical note

Funding Information:
* This paper presents the results of one phase of research carria,d oui at :he Jet Propulsion Laboratory, California Institute of Technology, under Contrxt No. NAS 7-100, sponsored by the National Aeronautics a1.d Space Administration. ** Original version received 15 November 1971.

Fingerprint

Dive into the research topics of 'On covering a product of sets with products of their subsets'. Together they form a unique fingerprint.

Cite this