Narrow Results

Given a graph $G=(V,E)$ and two positive integers j and k, an $L(j,k)$-edge-labeling is a function f assigning to edges of E colors from a set $\{\mathrm{0,1},\dots ,K_f\}$ such that $|f\left(e\right)-f(e\text{'})|\ge j$ if e and e^′ are adjacent, i.e. they share a common endpoint, $|f\left(e\right)-f(e\text{'})|\ge k$ if e and e^′ are not adjacent and there exists an edge adjacent to both e and e^′. The aim of the $L(j,k)$-edge-labeling problem consists of finding a coloring function f such that the value of $k_f$ is minimum. This minimum value is called ${\lambda }_{j,k}^{\prime }\left(G\right)$.

This problem has already been studied on hexagonal, squared and triangular grids, but mostly not coinciding upper and lower bounds on ${\lambda }_{j,k}^{\prime }$ have been proposed.

In this paper we close some of these gaps or find better bounds on ${\lambda }_{j,k}^{\prime }$ in the special cases $j=\mathrm{1,2}$ and $k=1$. Moreover, we propose tight $L(j,k)$-edge-labelings for eight-regular grids.

An interesting sequence of arrays on hierarchical hexagonal grids was employed by PYXIS Innovation Inc. for an efficient digital earth model. These arrays constitute a Cauchy sequence in terms of Hausdorff distance. In this paper, we show that the box-counting dimension for the boundary of the limit of this sequence is .