Partitioning the \(n\)-cube into sets with mutual distance 1 (Q1312006)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Partitioning the \(n\)-cube into sets with mutual distance 1 |
scientific article; zbMATH DE number 487989
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Partitioning the \(n\)-cube into sets with mutual distance 1 |
scientific article; zbMATH DE number 487989 |
Statements
Partitioning the \(n\)-cube into sets with mutual distance 1 (English)
0 references
9 April 1995
0 references
Assume that the vertices of the \(n\)-cube are partitioned in such a way that, given two subsets in the partition, there is always a vertex in one subset and a vertex in the other subset connected by an edge. Let \(m(n)\) be the maximal number of such subsets. In this paper it is proved that \((\sqrt 2/2)\sqrt{n2^ n}\leq m(n)\leq \sqrt{n2^ n}+ 1\). Furthermore, it is proposed to study the same problem for arbitrary graphs.
0 references
distance
0 references
\(n\)-cube
0 references
partition
0 references
