Minimal resolving sets for the hypercube

Details Minimal resolving sets for the hypercube Minimal resolving sets for the hypercube

2011-06-18

arxiv.org/abs/1106.3632v3

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Minimal resolving sets for the hypercube does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimal resolving sets for the hypercube, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimal resolving sets for the hypercube will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-465604