Distance two labeling for the strong product of two infinite paths

Yoomi Rho
Incheon National university

Byeong Kim
Gangneung-Wonju National University

Byung Song
Gangneung-Wonju National University

PDF

Minisymposium: GRAPH PRODUCTS

Content: An $L(h,k)$-labeling of a graph $G=(V,E)$ is a function $f$ on $V$ such that $|f(u)-f(v)|\ge h$ if ${\rm dist}(u,v)=1$ and $|f(u)-f(v)|\ge k$ if ${\rm dist}(u,v)=2$. The span of $f$ is the difference between the maximum and the minimum of $f$. The $L(h,k)$-labeling number $\lambda_{h,k}(G)$ of $G$ is the minimum span over all $L(h,k)$-labelings of $G$. Let $G$ be the strong product of two infinite paths. Calamoneri found lower bounds and upper bounds of $\lambda_{h,k}(G)$ for all $h$ and $k$ when $h\ge k$. Recently Kim et al. found a refined upper bound $3h+6k$ when $h\ge 4k$ and showed that it is the exact value when $h\ge 6k$. In this paper, we obtain lower bounds and upper bounds when $h<k$. Also we improve the result of Calamoneri when $k\le h\le 2k$.

Back to all abstracts