pith. sign in

arxiv: 1106.3632 · v3 · pith:HJ4IPSJUnew · submitted 2011-06-18 · 💻 cs.DM · math.CO

Minimal resolving sets for the hypercube

classification 💻 cs.DM math.CO
keywords resolvinghypercubeminimalsubsetverticesgraphproperrenyi
0
0 comments X
read the original abstract

For a given undirected graph $G$, an \emph{ordered} subset $S = {s_1,s_2,...,s_k} \subseteq V$ of vertices is a resolving set for the graph if the vertices of the graph are distinguishable by their vector of distances to the vertices in $S$. While a superset of any resolving set is always a resolving set, a proper subset of a resolving set is not necessarily a resolving set, and we are interested in determining resolving sets that are minimal or that are minimum (of minimal cardinality). Let $Q^n$ denote the $n$-dimensional hypercube with vertex set ${0,1}^n$. In Erd\"os and Renyi (Erdos & Renyi, 1963) it was shown that a particular set of $n$ vertices forms a resolving set for the hypercube. The main purpose of this note is to prove that a proper subset of that set of size $n-1$ is also a resolving set for the hypercube for all $n \ge 5$ and that this proper subset is a minimal resolving set.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.