Optimal $L(d,1)$-labeling of certain direct graph bundles cycles over cycles and Cartesian graph bundles cycles over cycles

Abstract

An $L(d,1)$-labeling of a graph $G$ is an assignment of nonnegative integers to the vertices such that adjacent vertices receive labels that differ by at least $d$ and those at a distance of two receive labels that differ by at least one, where $d\ge 1$. Let ${\lambda }_1^d(G)$ denote the least $\lambda$ such that $G$ admits an $L(d,1)$-labeling using labels from $\{0,1,\dots ,\lambda \}$. We prove that ${\lambda }_1^d(X)\le 2d+2$ for certain direct graph bundle $X=C_m{\times }^{{\sigma }_{\ell }}{C}_n$ and certain Cartesian graph bundle $X=C_m{\square }^{{\sigma }_{\ell }}{C}_n$, where ${\sigma }_{\ell }$ is a cyclic $\ell$-shift, with equality if $1\le d\le 4$.