A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid

Details A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid

2010-06-18

arxiv.org/abs/1006.3779v1

Electronic J. of Combinatorics, R113, Volume 16(1), 2009

Mathematics

Combinatorics

16 pages, 10 figures

Scientific paper

Given a graph $G$, an identifying code $C \subseteq V(G)$ is a vertex set such that for any two distinct vertices $v_1,v_2\in V(G)$, the sets $N[v_1]\cap C$ and $N[v_2]\cap C$ are distinct and nonempty (here $N[v]$ denotes a vertex $v$ and its neighbors). We study the case when $G$ is the infinite hexagonal grid $H$. Cohen et.al. constructed two identifying codes for $H$ with density $3/7$ and proved that any identifying code for $H$ must have density at least $16/39\approx0.410256$. Both their upper and lower bounds were best known until now. Here we prove a lower bound of $12/29\approx0.413793$.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-261335