| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Minimal resolving sets for the hypercube | Ashwin Ganesan
; | Date: |
18 Jun 2011 | Abstract: | Let $G=(V,E)$ be a simple, undirected graph. An ordered subset $S =
{s_1,s_2,...,s_k} subseteq V$ of vertices is a resolving set for $G$ if the
vertices of $G$ are distinguishable by their vector of distances to the
vertices in $S$. The $n$-dimensional hypercube $Q^n$ is the graph whose
vertices are the $2^n$ 0-1 sequences of length $n$, with two vertices being
adjacent whenever the corresponding two sequences differ in exactly one
coordinate. In cite{Erdos:Renyi:1963} it was shown that the vertices ${11...,
011..,$ $1011...1,..., 111...101}$ form a resolving set for the hypercube.
The purpose of this note is to prove that a proper subset of that set, namely
the vertices ${011...1, 1011...1,$ $..., 111...101}$, also forms a resolving
set for the hypercube for all $n ge 5$. | Source: | arXiv, 1106.3632 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |