On covering a product of sets with products of their subsets |
| |
Authors: | A.M. Odlyzko |
| |
Affiliation: | Massachusetts Institute of Technology, Cambridge, Mass. 02139, USA |
| |
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∈S1foralli. Moreo ver, these bounds cannot be improved. Identical bounds for the spanning number of a normal product of graphs are also obtained. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|