New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid

Details New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid

2011-10-05

arxiv.org/abs/1110.1097v1

Mathematics

Combinatorics

Scientific paper

For a graph, $G$, and a vertex $v \in V(G)$, let $N[v]$ be the set of vertices adjacent to and including $v$. A set $D \subseteq V(G)$ is a vertex identifying code if for any two distinct vertices $v_1, v_2 \in V(G)$, the vertex sets $N[v_1] \cap D$ and $N[v_2] \cap D$ are distinct and non-empty. We consider the minimum density of a vertex identifying code for the infinite hexagonal grid. In 2000, Cohen et al. constructed two codes with a density of $3/7 \approx 0.428571$, and this remains the best known upper bound. Until now, the best known lower bound was $12/29 \approx 0.413793$ and was proved by Cranston and Yu in 2009. We present three new codes with a density of 3/7, and we improve the lower bound to $5/12 \approx 0.416667$.

Affiliated with

Also associated with

No associations

Rating

New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid 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 New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-180380